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;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<ll,ll> P;

#define MAX_V 10000

struct edge{int to;long long cap,rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,long long 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<int> que;
	level[s] = 0;
	que.push(s);
	while(!que.empty())	{
		int v = que.front();que.pop();
		for(int i = 0;i < 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,long long f){
	if(v == t)return f;
	for(int &i = iter[v];i < G[v].size() ;++i){
		edge &e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to]){
			long long 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;
}

long long Dinic(int s,int t){
	long long flow = 0;
	while(1){
		bfs(s);
		if(level[t] < 0)return flow;
		memset(iter,0,sizeof(iter));
		long long f;while((f = dfs(s,t,INF)) > 0)flow += f;
	}
}

ll h, w, x;
ll mp[55][55];

int main(){

	cin >> h >> w >> x;
	ll ans = 0;
	REP(i, h){
		REP(j, w){
			cin >> mp[i][j];
			if(i > 0 && i < h - 1 && j > 0 && j < w - 1)ans += 2 * mp[i][j];
			else ans += mp[i][j];
		}
	}

	REP(i, h-1){
		REP(j, w-1){
			ll now = i * 50 + j;
			ll tmp;
			ll seica = mp[i][j] + mp[i+1][j] + mp[i][j+1] + mp[i+1][j+1];
			if(i % 2 == 0 && j % 2 == 0){
			//	cout << i << " " << j << endl;
				add_edge(2700, now, seica);
				add_edge(now, 2701, x);
			}
			if(i % 2 == 1 && j % 2 == 1){
			//	cout << i << " " << j << endl;
				add_edge(2700, now, x);
				add_edge(now, 2701, seica);
				tmp = (i-1) * 50 + (j-1);
				add_edge(tmp, now, mp[i][j]);
				tmp = (i+1) * 50 + (j-1);
				add_edge(tmp, now, mp[i+1][j]);
				tmp = (i-1) * 50 + (j+1);
				add_edge(tmp, now, mp[i][j+1]);
				tmp = (i+1) * 50 + (j+1);
				add_edge(tmp, now, mp[i+1][j+1]);
			}
		}
	}

	cout << ans - Dinic(2700, 2701) << endl;
	return 0;
}