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 <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};



// edge class (for network-flow)
template<class FLOWTYPE> struct Edge {
    int rev, from, to;
    FLOWTYPE cap, icap;
    Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap));
    }

    
    // debug
    friend ostream& operator << (ostream& s, const Graph& G) {
        s << endl; for (int i = 0; i < G.size(); ++i) { s << i << " : " << G.list[i] << endl; }return s;
    }
    
};

template<class FLOWTYPE> struct Dinic {
    const FLOWTYPE INF = 1LL<<59; // to be set
    vector<int> level, iter;

    Dinic() { }
    void dibfs(Graph<FLOWTYPE> &G, int s) {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int i = 0; i < G[v].size(); ++i) {
                Edge<FLOWTYPE> &e = G[v][i];
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    
    FLOWTYPE didfs(Graph<FLOWTYPE> &G, int v, int t, FLOWTYPE f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < G[v].size(); ++i) {
            Edge<FLOWTYPE> &e = G[v][i], &re = G.redge(e);
            if (level[v] < level[e.to] && e.cap > 0) {
                FLOWTYPE d = didfs(G, e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    re.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    FLOWTYPE solve(Graph<FLOWTYPE> &G, int s, int t) {
        level.assign((int)G.size(), -1); iter.assign((int)G.size(), 0);
        FLOWTYPE res = 0;
        while (true) {
            dibfs(G, s);
            if (level[t] < 0) return res;
            for (int i = 0; i < (int)iter.size(); ++i) iter[i] = 0;
            FLOWTYPE flow = 0;
            while ((flow = didfs(G, s, t, INF)) > 0) {
                res += flow;
            }
        }
    }
};

using pint = pair<int,int>;

long long N, M, W;
long long B[110][110];

map<pint,int> ma;

long long calc(int i, int j) {
    long long res = 0;
    for (int di = 0; di < 2; ++di) {
        for (int dj = 0; dj < 2; ++dj) {
            res += B[i+di][j+dj];
        }
    }
    return res;
}

int main() {
    while (cin >> N >> M >> W) {
        vector<pint> ls;
        long long ball = 0;
        long long wall = 0;
        ma.clear();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                cin >> B[i][j];
                ball += B[i][j];
                if ( i+1 < N && j+1 < M && (i + j) % 2 == 0 ) {
                    ls.push_back(pint(i, j));
                    wall += W;
                    ma[pint(i, j)] = 0;
                }
            }
        }
        int iter = 0;
        EACH(it, ma) it->second = iter++;

        long long INF = 1LL<<59;
        
        long long hiku = 0;
        Graph<long long> G(ma.size() + 4);
        int s = ma.size(), t = s + 1;
        int a = t + 1, b = a + 1;

        //G.addedge(s, a, INF);
        //G.addedge(b, t, INF);
        
        for (int i = 0; i < N-1; ++i) {
            for (int j = 0; j < M-1; ++j) {
                if (!ma.count(pint(i, j))) continue;
                int id = ma[pint(i, j)];

                if (i % 2 == 0) { // 白
                    G.addedge(s, id, calc(i, j));
                    G.addedge(id, t, W);
                }
                else {// 黒
                    G.addedge(s, id, W);
                    G.addedge(id, t, calc(i, j));
                }

                

                int ni = i + 1;
                for (int dj = -1; dj <= 1; dj += 2) {
                    int nj = j + dj;
                    if (!ma.count(pint(ni, nj))) continue;
                    int id2 = ma[pint(ni, nj)];

                    if (i % 2 == 0) { // 白
                        G.addedge(id, id2, B[i+1][(dj == -1 ? j : j+1)]);
                        //G.addedge(id, b, B[i+1][j]);
                        //G.addedge(a, id2, B[i+1][j]);
                    }
                    else { // 黒
                        G.addedge(id2, id, B[i+1][(dj == -1 ? j : j+1)]);
                        //G.addedge(id2, b, B[i+1][j+1]);
                        //G.addedge(a, id, B[i+1][j+1]);
                    }
                }
            }
        }

        Dinic<long long> din;
        long long res = din.solve(G, s, t);

        long long all = 0;
        for (int i = 0; i < N-1; ++i) {
            for (int j = 0; j < M-1; ++j) {
                if (!ma.count(pint(i, j))) continue;
                all += calc(i, j);
            }
        }

        cout << all - res << endl;

    }
}