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>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7;
const ll LINF=1e18;
using namespace std;
#define int long long
//template
struct Fordfulkerson{
  const int INF = LINF;
  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<int> used;

  Fordfulkerson(){}
  Fordfulkerson(int sz):n(sz),G(n),used(n){}

  void add_edge(int from,int to,int cap){
    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));
  }

  int dfs(int v,int t,int f){
    if(v==t) return f;
    used[v]=true;
    for(int i=0;i<(int)G[v].size();i++){
      edge &e = G[v][i];
      if(!used[e.to] && e.cap > 0 ){
        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(;;){
      fill(used.begin(),used.end(),0);
      int f=dfs(s,t,lim);
      if(f==0) return fl;
      fl+=f;
      lim-=f;
    }
  }

  int flow(int s,int t){
    return flow(s,t,INF);
  }

};
int B[60][60];
//main
signed main(){
  int h,w,W;cin>>h>>w>>W;
  for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin>>B[i][j];
  int ans=0;
  Fordfulkerson fl(10000);
  int x[4]={-1,-1,1,1};
  int y[4]={-1,1,-1,1};
  /*
  スイッチはスイッチの左上の電球の場所にあるとする
  左上の角と同じグループのスイッチはOnならSにつける
  もう片方のグループのスイッチはOffならSにつける
  */
  for(int i=0;i<h-1;i+=2){
    for(int j=0;j<w-1;j+=2){
      if(B[i][j]+B[i+1][j]+B[i][j+1]+B[i+1][j+1]<=W)continue;
      ans+=B[i][j]+B[i+1][j]+B[i][j+1]+B[i+1][j+1]-W;
      fl.add_edge(0,100*i+j+1,B[i][j]+B[i+1][j]+B[i][j+1]+B[i+1][j+1]-W);
      for(int k=0;k<4;k++){
        if(i+x[k]<0||i+x[k]>=h-1||j+y[k]<0||j+y[k]>=w-1)continue;
        if(B[i+x[k]][j+y[k]]+B[i+1+x[k]][j+y[k]]+B[i+x[k]][j+1+y[k]]+B[i+1+x[k]][j+1+y[k]]<=W)continue;
        int a=i,b=j;
        if(k==1)b++;
        if(k==2)a++;
        if(k==3){a++;b++;}
        fl.add_edge(100*i+j+1,100*(i+x[k])+j+y[k]+1,B[a][b]);
      }
    }
  }
  for(int i=1;i<h-1;i+=2){
    for(int j=1;j<w-1;j+=2){
      if(B[i][j]+B[i+1][j]+B[i][j+1]+B[i+1][j+1]<=W)continue;
      ans+=B[i][j]+B[i+1][j]+B[i][j+1]+B[i+1][j+1]-W;
      fl.add_edge(100*i+j+1,9999,B[i][j]+B[i+1][j]+B[i][j+1]+B[i+1][j+1]-W);
    }
  }
  cout<<ans-fl.flow(0,9999)<<endl;
}