#include "wombats.h"
#include <bits/stdc++.h>
#define eprintf(args...) fprintf(stderr, args)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)
const int mxn = 1 << 13;
int R, C;
int H[5000][200];
int V[5000][200];
struct O_o {
int l, r;
int dp[200][200];
O_o() { l = r = -1; memset(dp, 0x3f, sizeof(dp)); }
};
O_o operator + (const O_o &A, const O_o &B) {
if (A.l == -1) return B;
if (B.l == -1) return A;
O_o ans;
ans.l = A.l, ans.r = B.r;
assert(A.r == B.l);
rep(a, C) rep(b, C) rep(c, C)
ans.dp[a][c] = std::min(ans.dp[a][c], A.dp[a][b] + B.dp[b][c]);
return ans;
}
const int b = 4, B = 1 << b;
O_o S[mxn >> (b - 1)];
O_o get(int i) {
if (i + 1 >= R) return O_o();
O_o ans;
ans.l = i; ans.r = i + 1;
static int sum[2][200];
rep(c, 2) {
sum[c][0] = 0;
rep(j, C - 1) sum[c][j + 1] = sum[c][j] + H[i + c][j];
}
for (int a = 0; a < C; ++ a) {
int mn = 0x3f3f3f3f;
for (int b = a; b < C; ++ b) {
mn = std::min(mn, sum[0][b] - sum[0][a] + V[i][b] - sum[1][b]);
ans.dp[a][b] = mn + sum[1][b];
}
mn = 0x3f3f3f3f;
for (int b = a; b >= 0; -- b) {
mn = std::min(mn, sum[0][a] - sum[0][b] + V[i][b] + sum[1][b]);
ans.dp[a][b] = mn - sum[1][b];
}
}
return ans;
}
void update(int i) {
O_o ans;
for (int j = i; j < i + B; ++ j)
ans = ans + get(j);
S[(i >> b) + (mxn >> b)] = ans;
for (int x = (i >> b) + (mxn >> b); x >>= 1; ) {
S[x] = S[x << 1] + S[x << 1 | 1];
}
}
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
R = _R;
C = _C;
memcpy(H, _H, sizeof(H));
memcpy(V, _V, sizeof(V));
for (int i = 0; i << b <= R; ++ i) update(i << b);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
update(P >> b << b);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
update(P >> b << b);
}
int escape(int V1, int V2) {
return S[1].dp[V1][V2];
}
#ifdef DEBUG
#include "grader.c"
#endif
