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>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
const ll mod=1000000007;
const ll INF=1e15;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
struct edge{ ll to; ll cap; ll rev;};
const ll MAXN=2600;
vector<edge> G[MAXN];


const ll Start=2598, Goal=2599;
bool used[MAXN];

void addEdge0(ll from, ll to, ll cap){
    edge A={to,cap,(ll)G[to].size()};
    edge B={from,0,(ll)G[from].size()};
    G[from].push_back(A);
    G[to].push_back(B);
    return;
}//有向グラフを作る

void addEdge1(ll a, ll b, ll cap){
    edge A={b,cap,(ll)G[b].size()};
    edge B={a,cap,(ll)G[a].size()};
    G[a].push_back(A);
    G[b].push_back(B);
    return;
}//無向グラフを作る

ll dfs(ll v, ll t, ll f){
    if(v==t) return f;
    used[v]=true;
    rep(i,G[v].size()){
        edge &e=G[v][i];
        if(!used[e.to] && e.cap>0){
            ll 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;
}



ll MaxFlow(){
    ll ans=0;
    while(true){
        rep(i,MAXN) used[i]=false;
        ll P=dfs(Start,Goal,INF);
        if(P==0) break;
        ans+=P;
    }
    return ans;
}

ll h,w,W;
ll B[51][51];

ll bakkin(ll i,ll j){
    if(h==2 || w==2) return B[i][j]+B[i][j+1]+B[i+1][j]+B[i+1][j+1];
    ll ans=0;
    if(i==0) ans+= B[0][j]+B[0][j+1];
    if(i==h-2) ans+=B[h-1][j]+B[h-1][j+1];
    if(j==0) ans+=B[i][0]+B[i+1][0];
    if(j==w-2) ans+=B[i][w-1]+B[i+1][w-1];
    if(i*(h-2-i)==0 && j*(w-2-j)==0) {
        ll a=i, b=j;
        if(i!=0) a++;
        if(j!=0) b++;
        ans-=B[a][b];
    }
    //cout<<i<<' '<<j<<' '<<ans<<endl;
    return ans;
}

int main(){
    cin>>h>>w>>W;
    ll SUM=0;
    rep(i,h) rep(j,w) cin>>B[i][j];
    rep(i,h) rep(j,w) SUM+=B[i][j];

    rep(i,h-1) rep(j,w-1) if((i+j)%2==0){
        ll K=i*51+j;
        if(i%2==0) {addEdge0(Start,K,W); addEdge0(K,Goal,bakkin(i,j));}
        if(j%2==1) {addEdge0(K,Goal,W); addEdge0(Start,K,0);}
    }

    if(h>2 || w>2){
        for(ll i=1;i<h-1;i+=2){
            for(ll j=1;j<w-1;j+=2){
                ll K=i*51+j;
                addEdge0(K-52,K,B[i][j]);
                addEdge0(K-50,K,B[i][j+1]);
                addEdge0(K+50,K,B[i+1][j]);
                addEdge0(K+52,K,B[i+1][j+1]);
            }
        }
    }

    cout<<SUM-MaxFlow()<<endl;



}