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 unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

#define MAX_V 10000

struct edge{ ll to,cap,rev; };
vector<edge> G[MAX_V];
ll level[MAX_V];
int iter[MAX_V];

void add_edge(ll from,ll to,ll cap){
  // printf("%lld -> %lld : %lld\n", from,to,cap);
  G[from].push_back((edge){to,cap,(ll)G[to].size()});
  G[to].push_back((edge){from,0,(ll)G[from].size()-1});
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<ll> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    ll 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);
      }
    }
  }
}

ll dfs(int v,int t,ll 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]){
      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 max_flow(int s,int t){
  ll flow=0;
  while(1){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    ll f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll H,W,C;
  cin>>H>>W>>C;
  vector<vector<ll> > B(H,vector<ll>(W,0));
  rep(i,H)rep(j,W){
    cin>>B[i][j];
  }

  int source=(H-1)*(W-1);
  int sink=source+1;
  ll res=0;
  rep(i,H-1)rep(j,W-1){
    if((i+j)%2==1)continue;

    ll sum=0;
    repl(ni,i,i+2)repl(nj,j,j+2){
      sum+=B[ni][nj];
    }

    ll prof=sum-C;
    if(prof<0)continue;
    res+=prof;
    if(i%2==0){
      add_edge(source,i*(W-1)+j,0);
      add_edge(i*(W-1)+j,sink,prof);
    }else{
      add_edge(source,i*(W-1)+j,prof);
      add_edge(i*(W-1)+j,sink,0);
    }
  }

  rep(i,H)rep(j,W){
    if((i+j)%2==0){
      ll i1=i,j1=j,i2=i-1,j2=j-1;
      if(i1<0||j1<0||i1>=H-1||j1>=W-1)continue;
      if(i2<0||j2<0||i2>=H-1||j2>=W-1)continue;
      if(i1%2==1){
        add_edge(i1*(W-1)+j1,i2*(W-1)+j2,B[i][j]);
      }else{
        add_edge(i2*(W-1)+j2,i1*(W-1)+j1,B[i][j]);
      }
    }else{
      ll i1=i,j1=j-1,i2=i-1,j2=j;
      if(i1<0||j1<0||i1>=H-1||j1>=W-1)continue;
      if(i2<0||j2<0||i2>=H-1||j2>=W-1)continue;
      if(i1%2==1){
        add_edge(i1*(W-1)+j1,i2*(W-1)+j2,B[i][j]);
      }else{
        add_edge(i2*(W-1)+j2,i1*(W-1)+j1,B[i][j]);
      }
    }
  }

  cout<<res-max_flow(source,sink)<<endl;

  return 0;
}