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<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

#define int long long
const int INF=1e15;

struct Dinic{
    
    struct edge {
        int to,cap,rev;
        edge(){}
        edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}
    };
    
    int n;
    vector<vector<edge> > G;
    vector<map<int,int> > M;
    vector<int> level,iter;
    
    Dinic(){}
    Dinic(int sz):n(sz),G(n),M(n),level(n),iter(n){}
    
    void add_edge(int from,int to,int cap){
        M[from][to]=G[from].size();
        M[to][from]=G[to].size();
        G[from].push_back(edge(to,cap,G[to].size()));
        // undirected
        //G[to].push_back(edge(from,cap,G[from].size()-1));
        // directed
        G[to].push_back(edge(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.empty()){
            int v=que.front();que.pop();
            for(int i=0;i<(int)G[v].size();i++){
                edge &e = G[v][i];
                if(e.cap>0&&level[e.to]<0){
                    level[e.to]=level[v]+1;
                    que.push(e.to);
                }
            }
        }
    }
    
    int dfs(int v,int t,int f){
        if(v==t) return f;
        for(int &i=iter[v];i<(int)G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0&&level[v]<level[e.to]){
                int 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;
    }
    
    int flow(int s,int t,int lim){
        int fl=0;
        for(;;){
            bfs(s);
            if(level[t]<0||lim==0) return fl;
            fill(iter.begin(),iter.end(),0);
            int f;
            while((f=dfs(s,t,lim))>0){
                fl+=f;
                lim-=f;
            }
        }
    }
    
    int flow(int s,int t){
        return flow(s,t,INF);
    }
    
    //cap==1 only
    bool back_edge(int s,int t,int from, int to){
        for(int i=0;i<(int)G[from].size();i++) {
            edge& e=G[from][i];
            if(e.to==to) {
                if(e.cap==0&&flow(from,to,1)==0) {
                    flow(from,s,1);
                    flow(t,to,1);
                    return 1;
                }
            }
        }
        return 0;
    }
};

vector<ll> dx={0,1,0,1};
vector<ll> dy={0,0,1,1};

vector<ll> dx2={-1,1,-1,1};
vector<ll> dy2={-1,-1,1,1};


signed main(){
    ll h,w,W;
    cin>>h>>w>>W;
    vector<vector<ll>> A(h,vector<ll>(w));
    ll ans=0;
    for(auto &I:A){
        for(auto &T:I){cin>>T; ans+=T;}
    }
    Dinic F(h*w+10);
    ll s=h*w+3;
    ll g=s+1;
    for(int i=0;i+1<h;i++){
        for(int t=0;t+1<w;t++){
            if((i+t)&1){continue;}
            if(i&1){
                F.add_edge(i*w+t,g,W);
            }
            else{
                F.add_edge(s,i*w+t,W);
                ll cost=0;
                for(int j=0;j<4;j++){
                    ll x=i+dx[j];
                    ll y=t+dy[j];
                    if(x==0 || y==0 || x==h-1 || y==w-1){cost+=A[x][y];}
                    else{
                        F.add_edge(i*w+t,(i+dx2[j])*w+(t+dy2[j]),A[x][y]);
                    }
                }
                if(cost){F.add_edge(i*w+t,g,cost);}
            }
        }
    }
    cout<<ans-F.flow(s,g)<<endl;
    
    
    return 0;
}