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;

struct Dinic{
    struct edge {
        int64_t to, cap, rev;
        edge(int64_t to, int64_t cap, int64_t rev):to(to), cap(cap), rev(rev){}
    };

    int N, S, T;
    int64_t flow = 0;
    const int64_t INF = 1e18;
    vector<int> level, iter;
    vector<vector<edge>> G;

    Dinic(int N, int S, int T):N(N), S(S), T(T){
        flow = 0;
        level.resize(N);
        iter.resize(N);
        G.resize(N);
    }

    void add_edge(int from, int to, int64_t cap){
        G[from].emplace_back(to, cap, G[to].size());
        G[to].emplace_back(from, 0, G[from].size()-1);
    }

    void bfs(int s){
        fill(level.begin(), level.end(), -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(que.size()){
            int v = que.front(); que.pop();
            for(auto& e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    int64_t dfs(int v, int t, int64_t f){
        if(v == t) return f;
        for(int& i=iter[v]; i<G[v].size(); i++){
            auto& e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int64_t 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;
    }

    int64_t max_flow(){
        while(true){
            bfs(S);
            if(level[T] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            while(true){
                int64_t f = dfs(S, T, INF);
                if(f == 0) break;
                flow += f;
            }
        }
    }
};

int code(int i, int j){
    return i*50+j;
}

int main(){
    int H, W, C;
    int64_t B[50][50];
    cin >> H >> W >> C;
    for(int i=0; i<H; i++) for(int j=0; j<W; j++) cin >> B[i][j];

    int S = 2500, T = 2501;
    Dinic solver(T+1, S, T);

    int64_t ans = 0;
    for(int i=0; i<H-1; i++) for(int j=i%2; j<W-1; j+=2){
        int c = code(i, j);
        int64_t gain = B[i][j] + B[i][j+1] + B[i+1][j] + B[i+1][j+1] - C;
        if(gain <= 0) continue;
        ans += gain;
        if(i%2){
            solver.add_edge(c, T, gain);
        }else{
            solver.add_edge(S, c, gain);
        }
        if(i>0 && j>0){
            int c2 = code(i-1, j-1);
            if(i%2){
                solver.add_edge(c2, c, B[i][j]);
            }else{
                solver.add_edge(c, c2, B[i][j]);
            }
        }
        if(i>0 && j+1<W-1){
            int c2 = code(i-1, j+1);
            if(i%2){
                solver.add_edge(c2, c, B[i][j+1]);
            }else{
                solver.add_edge(c, c2, B[i][j+1]);
            }
        }
    }
    ans -= solver.max_flow();
    cout << ans << endl;
}