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;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;


template<class T> struct Dinic {
  struct Edge { int to, rev; T cap; };
  const int n;
  const T inf = numeric_limits<T>::max();
  VV<Edge> g;
  V<> dist, i;
  Dinic(int n) : n(n), g(n), dist(n), i(n) {}
  void add_edge(int from, int to, T cap) {
    assert(from != to);
    assert(cap >= 0);
    g[from].emplace_back(Edge{to, (int) g[to].size(), cap});
    g[to].emplace_back(Edge{from, (int) g[from].size() - 1, 0});
  }
  void bfs(int s) {
    fill(begin(dist), end(dist), -1);
    queue<int> que;
    dist[s] = 0;
    que.push(s);
    while (!que.empty()) {
      int v = que.front(); que.pop();
      for (const auto& e : g[v]) {
        if (dist[e.to] != -1 or e.cap <= 0) continue;
        dist[e.to] = dist[v] + 1;
        que.push(e.to);
      }
    }
  }
  T dfs(int v, int s, T f) {
    if (v == s) return f;
    for (; i[v] < g[v].size(); ++i[v]) {
      Edge& e = g[v][i[v]];
      if (dist[e.to] >= dist[v] or g[e.to][e.rev].cap <= 0) continue;
      T d = dfs(e.to, s, min(f, g[e.to][e.rev].cap));
      if (d > 0) {
        g[e.to][e.rev].cap -= d;
        e.cap += d;
        return d;
      }
    }
    return 0;
  }
  T max_flow(int s, int t) {
    assert(s != t);
    T res = 0;
    while (true) {
      bfs(s);
      if (dist[t] == -1) return res;
      fill(begin(i), end(i), 0);
      while (true) {
        T f = dfs(t, s, inf);
        if (f == 0) break;
        res += f;
      }
    }
  }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int h, w, c; cin >> h >> w >> c;
  VV<> b(h, V<>(w));
  for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
    cin >> b[i][j];
  }
  auto idx = [&](int i, int j) -> int {
    return i * (w - 1) + j >> 1;
  };
  int S = (h - 1) * (w - 1) + 1 >> 1, T = S + 1;
  Dinic<lint> g(T + 1);
  for (int i = 0; i < h - 1; i += 2) {
    for (int j = 0; j < w - 1; j += 2) {
      g.add_edge(S, idx(i, j), c);
      lint sum = 0;
      if (i == 0 or j == 0) sum += b[i][j];
      else g.add_edge(idx(i, j), idx(i - 1, j - 1), b[i][j]);
      if (i == 0 or j + 1 == w - 1) sum += b[i][j + 1];
      else g.add_edge(idx(i, j), idx(i - 1, j + 1), b[i][j + 1]);
      if (i + 1 == h - 1 or j == 0) sum += b[i + 1][j];
      else g.add_edge(idx(i, j), idx(i + 1, j - 1), b[i + 1][j]);
      if (i + 1 == h - 1 or j + 1 == w - 1) sum += b[i + 1][j + 1];
      else g.add_edge(idx(i, j), idx(i + 1, j + 1), b[i + 1][j + 1]);
      if (sum) g.add_edge(idx(i, j), T, sum);
    }
  }
  for (int i = 1; i < h - 1; i += 2) {
    for (int j = 1; j < w - 1; j += 2) {
      g.add_edge(idx(i, j), T, c);
    }
  }
  lint res = 0;
  for (int i = 0; i < h; ++i) {
    res += accumulate(begin(b[i]), end(b[i]), 0LL);
  }
  res -= g.max_flow(S, T);
  cout << res << '\n';
}