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 <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
#include <cmath>
#include <iomanip>
#include <array>
#include <string>
#include <stack>
#include <cassert>
#include <memory>
#include <random>
#include <fstream>
#include <cfloat>
#include <complex>

using namespace std;
struct Edge {
	int to, pair;
	long long int flow;
};
void set_depth(const vector<vector<Edge>>& nodes, vector<int>& depth, const int source) {
	queue<int> queue; queue.push(source);
	depth.assign(depth.size(), -1);
	depth[source] = 0;
	while (!queue.empty()) {
		const auto top = queue.front(); queue.pop();
		for (const auto e : nodes[top]) {
			if (e.flow > 0 && depth[e.to] == -1) {
				depth[e.to] = depth[top] + 1;
				queue.push(e.to);
			}
		}
	}
}
long long int push_flow(vector<vector<Edge>>& nodes, const vector<int>& depth, vector<int>& searching, const int current, const int sink, const long long int flow) {
	if (current == sink) {
		return flow;
	}
	else {
		while (searching[current] < nodes[current].size()) {
			const auto e = nodes[current][searching[current]];
			if (e.flow > 0 && depth[current] < depth[e.to]) {
				const auto f = push_flow(nodes, depth, searching, e.to, sink, min(flow, e.flow));
				if (f > 0) {
					nodes[current][searching[current]].flow -= f;
					nodes[e.to][e.pair].flow += f;
					return f;
				}
			}
			searching[current]++;
		}
		return 0;
	}
}
long long int max_flow(vector<vector<Edge>> nodes) {
	const auto sink = nodes.size() - 1;
	const auto source = sink - 1;
	vector<int> depth(nodes.size(), -1);
	vector<int> searching(nodes.size());
	long long int result = 0;
	bool has_flow = true;
	while (has_flow) {
		has_flow = false;
		set_depth(nodes, depth, source);
		searching.assign(nodes.size(), 0);
		long long int flow = 0;
		while (0 < (flow = push_flow(nodes, depth, searching, source, sink, LLONG_MAX))) {
			result += flow;
			has_flow = true;
		}
	}
	return result;
}
vector<vector<Edge>> make_nodes(const vector<vector<int>> supply, const int switch_cost) {
	vector<vector<Edge>> result;
	vector<vector<int>> index(supply.size(), vector<int>(supply[0].size(), -1));
	for (auto i = 0; i < supply.size() - 1; ++i) {
		for (auto j = 0; j < supply[i].size() - 1; ++j) {
			if (((i ^ j) & 1) == 0) {
				index[i][j] = result.size();
				result.push_back(vector<Edge>());
			}
		}
	}
	const auto source = result.size();
	const auto sink = source + 1;
	result.push_back(vector<Edge>());
	result.push_back(vector<Edge>());
	const auto add_edge = [&](const int from, const int to, const long long int flow) {
		result[from].push_back(Edge{ to, (int)result[to].size(), flow });
		result[to].push_back(Edge{ from, (int)result[from].size() - 1, 0 });
	};
	for (auto i = 0; i < supply.size() - 1; ++i) {
		for (auto j = 0; j < supply[i].size() - 1; ++j) {
			if (((i ^ j) & 1) == 0) {
				const auto sum_gain = (long long int)supply[i][j] + (long long int)supply[i][j + 1] + (long long int)supply[i + 1][j] + (long long int)supply[i + 1][j + 1] - switch_cost;
				if (sum_gain <= 0) continue;
				if ((i & 1) == 0) {
					add_edge(source, index[i][j], sum_gain);
				}
				else {
					add_edge(index[i][j], sink, sum_gain);
					continue;
				}
				if (i > 0) {
					if (j > 0) add_edge(index[i][j], index[i - 1][j - 1], supply[i][j]);
					if (j + 2 < supply[i].size()) add_edge(index[i][j], index[i - 1][j + 1], supply[i][j + 1]);
				}
				if (i + 2 < supply.size()) {
					if (j > 0) add_edge(index[i][j], index[i + 1][j - 1], supply[i + 1][j]);
					if (j + 2 < supply[i].size()) add_edge(index[i][j], index[i + 1][j + 1], supply[i + 1][j + 1]);
				}
			}
		}
	}
	return result;
}
int main() {
	int height, width, switch_cost; cin >> height >> width >> switch_cost;
	vector<vector<int>> lamps(height, vector<int>(width));
	for (auto& line : lamps) {
		for (auto& cell : line) {
			cin >> cell;
		}
	}
	long long int initial_gain = 0;
	for (auto i = 0; i < height - 1; ++i) {
		for (auto j = 0; j < width - 1; ++j) {
			if (((i + j) & 1) == 0) {
				long long int sum_gain = (long long int)lamps[i][j] + (long long int)lamps[i + 1][j] + (long long int)lamps[i][j + 1] + (long long int)lamps[i + 1][j + 1] - switch_cost;
				if (sum_gain > 0) {
					initial_gain += sum_gain;
				}
			}
		}
	}
	auto nodes = make_nodes(move(lamps), switch_cost);
	const auto min_loss = max_flow(move(nodes));
	cout << initial_gain - min_loss << endl;
}