#include #define INF 0x3f3f3f3f const int MAXN = 2e5 + 5; const int MAXM = 1e6 + 5; struct Edge { int To, Cap, Next; } edge[MAXM << 1]; int head[MAXN], tot = 1; void Addedge(int u, int v, int w) { edge[++tot].Next = head[u], edge[tot].To = v, edge[tot].Cap = w, head[u] = tot; edge[++tot].Next = head[v], edge[tot].To = u, edge[tot].Cap = 0, head[v] = tot; } int cur[MAXN], dep[MAXN], que[MAXN], qhead, qtail; int n, m, s, t; int addx[] = {0, 0, 1, -1, 0}; int addy[] = {1, -1, 0, 0, 0}; int ans; int Min(int x, int y) { return x < y ? x : y; } bool bfs(bool limit) { for(int i = s; i <= t; i++) dep[i] = 0, cur[i] = head[i]; qhead = 1; qtail = 1; que[1] = t; dep[t] = 1; while(qhead <= qtail) { int u = que[qhead++]; for(int i = head[u]; i; i = edge[i].Next) { int v = edge[i].To; if(!dep[v] && edge[i ^ 1].Cap && (!limit || !(i & 1))) { dep[v] = dep[u] + 1; que[++qtail] = v; if (v == s) return 1; } } } return 0; } int dfs(int u, int flow) { if(u == t || !flow) return flow; int rest = flow; for(int i = cur[u]; i && rest; i = edge[i].Next) { cur[u] = i; int v = edge[i].To; if(dep[v] == dep[u] - 1 && edge[i].Cap) { int del = dfs(v, Min(rest, edge[i].Cap)); rest -= del; edge[i].Cap -= del; edge[i ^ 1].Cap += del; if(!del) dep[v] = -2; } } return flow - rest; } int Dinic() { int res = 0, flow; while (bfs(1)) while ((flow = dfs(s, INF))) res += flow; while (bfs(0)) while ((flow = dfs(s, INF))) res += flow; return res; } int Get(int x, int y, int h) { return (x - 1) * m + y + n * m * h; } int main() { scanf("%d %d", &n, &m); s = 0, t = 4 * n * m + 1; for (int i = 1; i <= n; i++) { for (int j = 1, a; j <= m; j++) { scanf("%d", &a); Addedge(Get(i, j, 0), t, a); ans += a; } } for (int i = 1; i <= n; i++) { for (int j = 1, a; j <= m; j++) { scanf("%d", &a); Addedge(s, Get(i, j, 1), a); Addedge(Get(i, j, 1), Get(i, j, 0), INF); ans += a; } } for (int i = 1; i <= n; i++) { for (int j = 1, a; j <= m; j++) { scanf("%d", &a); Addedge(Get(i, j, 2), t, a); ans += a; for (int k = 0; k < 5; k++) { int ni = i + addx[k]; int nj = j + addy[k]; if (ni < 1 || ni > n || nj < 1 || nj > m) continue; Addedge(Get(ni, nj, 0), Get(i, j, 2), INF); } } } for (int i = 1; i <= n; i++) { for (int j = 1, a; j <= m; j++) { scanf("%d", &a); ans += a; Addedge(s, Get(i, j, 3), a); for (int k = 0; k < 5; k++) { int ni = i + addx[k]; int nj = j + addy[k]; if (ni <= 1 || ni >= n || nj <= 1 || nj > m) continue; Addedge(Get(i, j, 3), Get(ni, nj, 1), INF); } } } printf("%d", ans - Dinic()); return 0; }