Problem: problem

There is a light bulb at the grid point $ (x, y) $ that meets $ 1 \ leq x \ leq h, 1 \ leq y \ leq w $.

The power supply is installed at coordinates $ (i + 0.5, j + 0.5) (1 \ leq i <h, 1 \ leq j <w, i + j $ is even) (corrected at 14:21). Coordinates $ When the power supply installed at (i + 0.5, j + 0.5) $ is turned on, the coordinates $ (i, j), (i + 1, j), (i, j + 1), (i + 1) , j + 1) $ 4 $ light bulbs in $ glow.

If you have more than $ 1 $ connected to a power supply with a light bulb on $ (i, j) $, you get $ B_ {i, j} $ cleanliness. You have the total cleanliness. Also, if you turn on each power supply, it costs $ W $ for electricity per $ 1 $.

Turn on some power to maximize "total income-total electricity bill".



output

Output the maximum value of "total income-total electricity bill". Also, output a line break at the end.

Example

Input

4 4 10
100 100 100 100
100 100 100 100
1 100 100 1
1 1 1 1


Output

970

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define REP(i, n) for(int i=0;i<(int)n;++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

typedef ll Weight;

struct Edge {
    int src, dst;
    Weight weight;

    Edge(int src, int dst, Weight weight) :
            src(src), dst(dst), weight(weight) {}
};

bool operator<(const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
           e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

const ll INF = 1e18;


#define RESIDUE(s, t) (capacity[s][t]-flow[s][t])

Weight maximumFlow(const Graph &g, int s, int t) {
    int n = g.size();
    Matrix flow(n, Array(n)), capacity(n, Array(n));
    REP(u, n) FOR(e, g[u]) capacity[e->src][e->dst] += e->weight;

    Weight total = 0;
    while (1) {
        queue<int> Q;
        Q.push(s);
        vector<int> prev(n, -1);
        prev[s] = s;
        while (!Q.empty() && prev[t] < 0) {
            int u = Q.front();
            Q.pop();
            FOR(e, g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) {
                    prev[e->dst] = u;
                    Q.push(e->dst);
                }
        }
        if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side
        Weight inc = INF;
        for (int j = t; prev[j] != j; j = prev[j])
            inc = min(inc, RESIDUE(prev[j], j));
        for (int j = t; prev[j] != j; j = prev[j])
            flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
        total += inc;
    }
}

Graph g;

void add(int a, int b, int f) {
    g[a].push_back(Edge(a, b, f));
    g[b].push_back(Edge(b, a, 0));
}


ll B[55 * 55];


vector<int> E[55 * 55];

int parity[55 * 55];

int main() {
    int h, w;
    ll W;
    cin >> h >> w >> W;

    ll ans = 0;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> B[i * w + j];
            ans += B[i * w + j];
        }
    }

    auto id = [&](int y, int x) {
        return y * w + x;
    };

    g.resize(h * w + 2);
    int ss = g.size() - 1;
    int tt = g.size() - 2;


    int K = 0;
    for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w - 1; j++) {
            if ((i + j) % 2) continue;
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 2; l++) {
                    if (i + k >= h || j + l >= w) continue;
                    E[id(i + k, j + l)].push_back(K);
                }
            }
            parity[K] = i % 2;
            if (i % 2 == 0) {
                add(ss, K, 0);
                add(K, tt, W);
            } else {
                add(ss, K, W);
                add(K, tt, 0);
            }
            K++;
        }
    }

    for (int k = 0; k < 55 * 55; k++) {
        auto es = E[k];


        if (es.size() == 0) continue;
        if (es.size() == 2) {
            assert(parity[es[0]] != parity[es[1]]);
            if( parity[es[0]] > parity[es[1]] ) swap(es[0], es[1]);
            add(es[1], es[0], B[k]);
        } else {
            assert(es.size() == 1);
            if( parity[es[0]] == 0 ) {
                add(ss, es[0], B[k]);
            }else{
                add(es[0], tt, B[k]);
            }
        }
    }

    cout << ans - maximumFlow(g, ss, tt) << endl;

}