- #include#include#include#define inf 19260817 using namespace std;#define rep(a, b, c) for (rg int a = b; a <= c; a++)#define drep(a, b, c) for (rg int a = b; a >= c; a--)#define erep(a, b) for (rg int a = fir[b]; a; a = nxt[a])#define il inline#define rg register#define vd void#define t(dis[i]) typedef long long ll;
- il int gi() {
- rg int x = 0;
- rg char ch = getchar();
- while (ch < '0' || ch > '9') ch = getchar();
- while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0',
- ch = getchar();
- return x;
- }
- const int maxn = 10005,
- S = 10001,
- T = 10002,
- maxm = 10010 * 12;
- int id = 1,
- fir[maxn],
- dis[maxm],
- nxt[maxm],
- w[maxm];
- il vd add(int a, int b, int c) {
- nxt[++id] = fir[a],
- fir[a] = id,
- dis[id] = b,
- w[id] = c;
- if (c) add(b, a, 0);
- }
- int num[101][101],
- C[101][101],
- dep[maxn],
- head[maxn];
- il bool BFS() {
- rg int que[maxn],
- hd = 0,
- tl = 1;
- memset(dep, 0, sizeof dep);
- que[hd] = S,
- dep[S] = 1;
- while (hd - tl) {
- int now = que[hd++];
- erep(i, now) if (!dep[t] && w[i]) que[tl++] = t,
- dep[t] = dep[now] + 1;
- }
- return dep[T];
- }
- il int Dinic(int now, int maxflow) {
- if (now == T) return maxflow;
- rg int ret = 0;
- for (rg int & i = head[now]; i; i = nxt[i]) if (w[i] && dep[t] == dep[now] + 1) {
- rg int d = Dinic(t, min(maxflow, w[i]));
- w[i] -= d,
- w[i ^ 1] += d,
- maxflow -= d,
- ret += d;
- if (!maxflow) break;
- }
- return ret;
- }
- int main() {
- rg int n = gi(),
- m = gi(),
- sum = 0,
- a;
- rep(i, 1, n) rep(j, 1, m) num[i][j] = ++num[0][0];
- rep(i, 1, n) rep(j, 1, m) {
- a = gi(),
- sum += a;
- if ((i + j) & 1) add(S, num[i][j], a);
- else add(num[i][j], T, a);
- }
- rep(i, 1, n) rep(j, 1, m) {
- a = gi(),
- sum += a;
- if ((i + j) & 1) add(num[i][j], T, a);
- else add(S, num[i][j], a);
- }
- rep(i, 1, n) rep(j, 1, m) {
- C[i][j] = gi();
- if (i - 1) sum += C[i][j];
- if (j - 1) sum += C[i][j];
- if (i - n) sum += C[i][j];
- if (j - m) sum += C[i][j];
- }
- rep(i, 1, n) rep(j, 1, m) {
- if (i - 1) add(num[i][j], num[i - 1][j], C[i][j] + C[i - 1][j]);
- if (j - 1) add(num[i][j], num[i][j - 1], C[i][j] + C[i][j - 1]);
- if (i - n) add(num[i][j], num[i + 1][j], C[i][j] + C[i + 1][j]);
- if (j - m) add(num[i][j], num[i][j + 1], C[i][j] + C[i][j + 1]);
- }
- while (BFS()) memcpy(head, fir, sizeof head),
- sum -= Dinic(S, inf);
- printf("%d\n", sum);
- return 0;
- }