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 int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



//Dinic

#define SIZE 2500


//辺を表す構造体(行先、容量、逆辺のインデックス)
struct Edge{
	Edge(int arg_to,ll arg_capacity,ll arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		rev_index = arg_rev_index;
	}
	int to,rev_index;
	ll capacity;
};



int V,E;
int H,W;
int dist[SIZE]; //sourceからの距離
int cheked_index[SIZE]; //どこまで調べ終わったか
int index_table[70][70];
int diff_row[4] = {-1,-1,1,1},diff_col[4] = {-1,1,-1,1};
ll value[70][70];
vector<Edge> G[SIZE]; //グラフの隣接リスト表現


bool rangeCheck(int row,int col){

	return row >= 1 && row <= H-1 && col >= 1 &&col <= W-1;
}


void add_edge(int from,int to,ll capacity){
	G[from].push_back(Edge(to,capacity,G[to].size()));
	G[to].push_back(Edge(from,0,G[from].size()-1)); //逆辺の、初期容量は0
}

//sourceからの最短距離をBFSで計算する
void bfs(int source){
	for(int i = 0; i < V; i++)dist[i] = -1;
	queue<int> Q;
	dist[source] = 0;
	Q.push(source);

	while(!Q.empty()){
		int node_id = Q.front();
		Q.pop();
		for(int i = 0; i < G[node_id].size(); i++){
			Edge &e = G[node_id][i];
			if(e.capacity > 0 && dist[e.to] < 0){ //辺の容量が正で、かつエッジの行先に未訪問の場合
				dist[e.to] = dist[node_id]+1;
				Q.push(e.to);
			}
		}
	}
}

//増加パスをDFSで探す
ll dfs(int node_id,int sink,ll flow){
	if(node_id == sink)return flow; //終点についたらflowをreturn

	for(int &i = cheked_index[node_id]; i < G[node_id].size(); i++){ //node_idから出ているエッジを調査
		Edge &e = G[node_id][i];
		if(e.capacity > 0 && dist[node_id] < dist[e.to]){ //流せる余裕があり、かつsourceからの距離が増加する方法である場合
			ll tmp_flow = dfs(e.to,sink,min(flow,e.capacity)); //流せるだけ流す
			if(tmp_flow > 0){ //流せた場合
				e.capacity -= tmp_flow; //流した分、エッジの容量を削減する
				G[e.to][e.rev_index].capacity += tmp_flow; //逆辺の容量を、流した分だけ増加させる
				return tmp_flow;
			}
		}
	}
	return 0;
}


ll max_flow(int source,int sink){ //source:始点 sink:終点
	ll flow = 0,add;
	while(true){ //増加パスが存在する限り、流量を追加し続ける
		bfs(source);
		if(dist[sink] < 0)break; //sourceからsinkへと辿り着く残余グラフがない、つまり増加パスが無くなった場合、break
		for(int i = 0; i < V; i++)cheked_index[i] = 0;
		while((add = dfs(source,sink,HUGE_NUM)) > 0){ //増加パスが見つかる間、加算
			flow += add;
		}
	}
	return flow;
}



int main(){

	ll COST;

	scanf("%d %d %lld",&H,&W,&COST);

	for(int row = 1; row <= H; row++){
		for(int col = 1; col <= W; col++){

			scanf("%lld",&value[row][col]);
		}
	}

	int index = 0;

	for(int row = 1; row <= H-1; row++){
		for(int col = 1; col <= W-1; col++){
			if((row+col)%2 == 1)continue;

			index_table[row][col] = index++;
		}
	}

	int source = index++,sink = index++;
	V = index;

	ll sum = 0;

	for(int row = 1; row <= H-1; row++){
		for(int col = 1; col <= W-1; col++){
			if((row+col)%2 == 1)continue;

			ll tmp = value[row][col]+value[row][col+1]+value[row+1][col]+value[row+1][col+1]-COST;
			if(tmp > 0){

				sum += tmp;
			}

			if(col%2 == 1){

				add_edge(source,index_table[row][col],0);
				add_edge(index_table[row][col],sink,tmp);

			}else{

				add_edge(source,index_table[row][col],tmp);
				add_edge(index_table[row][col],sink,0);
			}
		}
	}

	for(int row = 1; row <= H-1; row++){
		for(int col = 1; col <= W-1; col++){
			if((row+col)%2 == 1 || col%2 == 1)continue;

			for(int i = 0; i < 4; i++){

				int adj_row = row+diff_row[i];
				int adj_col = col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				ll cap;

				switch(i){
				case 0:
					cap = value[row][col];
					break;
				case 1:
					cap = value[row][col+1];
					break;
				case 2:
					cap = value[row+1][col];
					break;
				case 3:
					cap = value[row+1][col+1];
					break;
				}

				add_edge(index_table[row][col],index_table[adj_row][adj_col],cap);
			}
		}
	}

	printf("%lld\n",sum-max_flow(source,sink));

	return 0;
}