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;
const ll INF = 1e16;

template<typename flow>
struct max_flow {
    struct edge {
        int to;
        flow cap;
        int rev; 
    };
    int V;
    vector<vector<edge> > G;
    vector<int> itr, level;

    max_flow(int V) :V(V) {G.assign(V, vector<edge>()); }

    void add_edge(int from, int to, flow cap) {
        //cerr << "from " << from << " to " << to << " : " << cap << endl;
        G[from].push_back((edge){to, cap, (int)G[to].size()});
        G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
    }

    void bfs(int s) {
        level.assign(V, -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while(!q.empty()) {
            int v = q.front(); q.pop();
            for(auto &e:G[v]) {
                if(e.cap > 0 and level[e.to] < 0) {
                    level[e.to] = level[v]+1;
                    q.push(e.to);
                }
            }
        }
    }
    flow dfs(int v, int t, flow f) {
        if(v == t) return f;
        for(int &i = itr[v]; i < (int) G[v].size(); ++i) {
            edge& e = G[v][i];
            if(e.cap > 0 and level[v] < level[e.to]) {
                flow d = dfs(e.to, t, min(f, e.cap));
                if(d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    flow run(int s, int t) {
        flow ret = 0, f;
        while(bfs(s), level[t] >= 0) {
            itr.assign(V, 0);
            while((f = dfs(s, t, INF)) > 0) ret += f;
        }
        return ret;
    }
};

ll to_point(int i, int j) {
    return i * 1000 + j;
}
ll B[105][105];
int main() {
    int h, w;
    cin >> h >> w;
    ll W;
    cin >> W;
    ll ans = 0;
    for(int i = 0; i < 2 * h; i+=2) {
        for(int j = 0; j < 2*w; j+=2) {
            cin >> B[i][j];
            ans += B[i][j];
        }
    }
    const int source = 0;
    const int target = 200040;
    max_flow<ll> field(200500);
    //onlyをはる
    /*ll one_val = B[0][0] + B[2][0] + B[0][2];
    field.add_edge(to_point(1, 1), target, one_val);
    if(h>2) {
        one_val = B[2*h-4][0] + 
    }
    for(int i = 5; i <= 2 * (h - 1); i+=4) {
        ll val = B[i-1][0]+B[i+1][0];
        field.add_edge(to_point(i, 1), target, val);
    }
    for(int i = 5; i <= 2 * (w - 1); i+=4) {
        ll val = B[0][i-1]+B[0][i+1];
        field.add_edge(to_point(1, i), target, val);
    }
    */
    for(int i = 2; i < 2 * (h - 1); i += 2) {
        int newi;
        if(i % 4 == 2) newi = i - 1;
        else newi = i + 1;
        field.add_edge(to_point(newi, 1), target, B[i][0]);
        field.add_edge(to_point(newi, 2*w-3), target, B[i][2*w-2]);
    }
    for(int i = 2; i < 2 * (w - 1); i += 2) {
        int newi;
        if(i % 4 == 2) newi = i - 1;
        else newi = i + 1;
        field.add_edge(to_point(1, newi), target, B[0][i]);
        field.add_edge(to_point(2*h-3, newi), target, B[2*h-2][i]);
    }
    field.add_edge(to_point(1, 1), target, B[0][0]);
    field.add_edge(to_point(1, 2 * w-3), target, B[0][2*w-2]);
    field.add_edge(to_point(2*h-3, 1), target, B[2*h-2][0]);
    field.add_edge(to_point(2*h-3, 2*w-3), target, B[2*h-2][2*w-2]);
    //onlyここまで
    //Wをはる
    for(int i = 1; i < 2 * (h-1); i+=2) {
        for(int j = 1; j < 2 * (w-1); j+=2) {
            if((i + j) % 4 != 2) continue;
            if(i % 4 == 1) field.add_edge(source, to_point(i, j), W);
            else field.add_edge(to_point(i, j), target, W);
        }
    }
    //Wここまで
    //共有するBをはる
    int di[4] = {1, 1, -1, -1};
    int dj[4] = {1, -1, 1, -1};
    for(int i = 1; i <= 2 * (h - 1); i += 4) {
        for(int j = 1; j <= 2 * (w - 1); j+=4) {
            for(int k = 0; k < 4; k++) {
                int light_i = i + di[k];
                int light_j = j + dj[k];
                int generator_i = i + 2 * di[k];
                int generator_j = j + 2 * dj[k];
                if(generator_i < 0 || generator_i > 2 * (h - 1) || generator_j < 0 || generator_j > 2 * (w - 1)) continue;
                field.add_edge(to_point(i, j), to_point(generator_i, generator_j), B[light_i][light_j]);
            }
        }
    }
    //共有するBここまで
    cout << ans - field.run(source, target) << endl;
}