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;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

const ll INF = 1ll<<60;
// Dinic http://www.prefield.com/algorithm/graph/dinic.html
struct dinic{
  struct edge{int to;ll cost;};
  int n;
  vector< vector<edge> > G;
  vector<vl> flow, capacity;
#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
  vi level;
  vector<bool> finished;
  dinic(int _n){
    n = _n;
    G.assign(n,vector<edge>());
    flow.assign(n,vl(n,0));
    capacity.assign(n,vl(n,0));
    level.assign(n,0);
    finished.assign(n,false);
  }
  void add_edge(int from,int to,ll cost){
    assert(0<=from && from<n);
    assert(0<=to && to<n);
    G[from].push_back((edge){to,cost});
    G[to].push_back((edge){from,0ll});  // 逆に流すフローのためのダミー辺
  }
  ll dfs(int u, int t, ll cur){
    if(u==t || cur==0) return cur;
    if(finished[u]) return 0;
    finished[u] = true;
    REP(i,G[u].size()){
      edge e = G[u][i];
      if(level[e.to] > level[u]){
        ll f = dfs(e.to, t, min(cur, RESIDUE(u,e.to)));
        if(f>0){
          flow[u][e.to] += f;
          flow[e.to][u] -= f;
          finished[u] = false;
          return f;
        }
      }
    }
    return 0;
  }
  ll calc(int s, int t){
    REP(i,n)REP(j,n)flow[i][j]=capacity[i][j]=0;
    REP(u,n)REP(j,G[u].size()){
      edge e = G[u][j];
      capacity[u][e.to] += e.cost;
    }
    ll total = 0;
    while(true){
      REP(i,n)level[i] = -1;
      level[s] = 0;
      queue<int> Q; Q.push(s);
      int d = n;
      while(!Q.empty()){
        int u = Q.front(); Q.pop();
        REP(i,G[u].size()){
          edge e = G[u][i];
          if(RESIDUE(u,e.to) > 0 && level[e.to] == -1){
            Q.push(e.to);
            level[e.to] = level[u] + 1;
          }
        }
      }
      REP(i,n)finished[i]=false;
      bool flag = false;
      while(true){
        ll f = dfs(s,t,INF);
        if(f==0)break;
        total += f;
        flag = true;
      }
      if(!flag)break;
    }
    return total;
  }
};

int h,w,W;
int b[52][52];

int main(){
  scanf("%d%d%d",&h,&w,&W);
  REP(i,h)REP(j,w)scanf("%d",&b[i][j]);

  map<pii,int> M;
  int it = 0;
  FOR(i,-1,h)FOR(j,-1,w)if((i+j)%2==0){
    M[pii(i,j)] = it++;
  }
  const int S = it++;
  const int T = it++;
  dinic D(it);

  FOR(i,-1,h)FOR(j,-1,w)if((i+j)%2==0){
    int id = M[pii(i,j)];
    bool out = i==-1 || j==-1 || i==h-1 || j==w-1;
    if(i%2==0){
      // on off
      D.add_edge(S,id,out ? INF : (ll)W);
      D.add_edge(id,T,0);
    }else{
      // off on
      D.add_edge(S,id,0);
      D.add_edge(id,T,out ? INF : (ll)W);
    }
  }
  REP(i,h)REP(j,w){
    int lid, rid;
    if(i%2==0 && j%2==0){
      lid = M[pii(i,j)];
      rid = M[pii(i-1,j-1)];
    }else if(i%2==1 && j%2==1){
      lid = M[pii(i-1,j-1)];
      rid = M[pii(i,j)];
    }else if(i%2==0 && j%2==1){
      lid = M[pii(i,j-1)];
      rid = M[pii(i-1,j)];
    }else{
      lid = M[pii(i-1,j)];
      rid = M[pii(i,j-1)];
    }
    D.add_edge(lid,rid,b[i][j]);
  }
  ll ans = 0;
  REP(i,h)REP(j,w)ans += b[i][j];
  ans -= D.calc(S,T);
  printf("%lld\n",ans);
  return 0;
}