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 <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
template<typename T> class Dinic {
private:
	struct edge {
		int to;
		T cap;
		int rev;
	};
	int V;
	vector<vector<edge> > G;
	vector<int> level, iter;
	void bfs(int s) {
		fill(level.begin(), level.end(), -1);
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front();
			que.pop();
			for (auto& e : G[v]) {
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}
	T dfs(int v, int t, T 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]) {
				T 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;
	}

public:
	Dinic(int node_size) : V(node_size), G(V), level(V), iter(V) {}
	//辺を張る
	void add_edge(int from, int to, T cap) {
		G[from].push_back((edge) { to, cap, (int)G[to].size() });
		G[to].push_back((edge) { from, (T)0, (int)G[from].size() - 1 });
	}
	//最大流を計算
	T solve(int s, int t) {
		T flow = 0;
		for (;;) {
			bfs(s);
			if (level[t] < 0) return flow;
			fill(iter.begin(), iter.end(), 0);
			T f;
			while ((f = dfs(s, t, numeric_limits<T>::max())) > 0) {
				flow += f;
			}
		}
	}
};
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H, W, C;
	cin >> H >> W >> C;
	vector<vector<int> > A(H, vector<int>(W));
	int sum = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> A[i][j];
			sum += A[i][j];
		}
	}

	int N = H * W + (H - 1) * (W - 1) + 2;


	int s = N - 2;
	int t = N - 1;


	Dinic<int> d(N);
	int INF = (int)1 << 50;
	vector<int> dc(H*W, 0);
	vector<int> sc(H*W, 0);

	for (int i = 0; i < H - 1; i++) {
		for (int j = 0; j < W - 1; j++) {

			if ((i + j) % 2 == 0) {
				int idx = H * W + i * (W - 1) + j;
				if (i % 2 == 0) {
					d.add_edge(s, idx, C);
					for (int x = 0; x < 2; x++) {
						for (int y = 0; y < 2; y++) {
							d.add_edge(idx, (i + x) * W + j + y, A[i + x][j + y]);
							dc[(i + x) * W + j + y]++;
						}
					}
				}
				else {
					for (int x = 0; x < 2; x++) {
						for (int y = 0; y < 2; y++) {
							d.add_edge((i + x) * W + j + y, idx, A[i + x][j + y]);
							sc[(i + x) * W + j + y]++;
						}
					}
					d.add_edge(idx, t, C);

				}
			}
		}
	}


	for (int i = 0; i < H * W; i++) {
		if (dc[i] == 0) {
			d.add_edge(s, i, INF);
		}
		if (sc[i] == 0) {
			d.add_edge(i, t, INF);
		}
	}
	int res = sum - d.solve(s, t);




	cout << res << endl;
}