#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;
static int pr[205][205];
rep(i, C) rep(j, C) pr[i][j] = -1;
for (int delta = -(C - 1); delta <= (C - 1); ++ delta) {
for (int a = 0; a < C; ++ a) {
int b = a + delta;
if (b >= 0 && b < C) {
int L = b ? pr[a][b - 1] : 0;
int R = a + 1 < C ? pr[a + 1][b] : C - 1;
for (int c = L; c <= R; ++ c) {
if (ans.dp[a][b] > A.dp[a][c] + B.dp[c][b]) {
ans.dp[a][b] = A.dp[a][c] + B.dp[c][b];
pr[a][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] = std::min(ans.dp[a][b], mn + sum[1][b]);
}
mn = 0x3f3f3f3f;
for (int b = 0; b < C; ++ b) {
if (b <= a) mn = std::min(mn, sum[0][a] - sum[0][b] + V[i][b] - sum[1][b]);
ans.dp[a][b] = std::min(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] = std::min(ans.dp[a][b], mn - sum[1][b]);
}
mn = 0x3f3f3f3f;
for (int b = C - 1; b >= 0; -- b) {
if (b >= a) mn = std::min(mn, sum[0][b] - sum[0][a] + V[i][b] + sum[1][b]);
ans.dp[a][b] = std::min(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;
if (P && ((P - 1) >> b) != (P >> b)) update((P - 1) >> b << b);
update(P >> b << b);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
update(P >> b << b);
if ((P >> b) != ((P + 1) >> b)) update((P + 1) >> b << b);
}
int escape(int V1, int V2) {
return S[1].dp[V1][V2];
}
#ifdef DEBUG
#include "grader.c"
#endif
