#include "wombats.h"
#include <bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;
int A[5001][201], B[5001][201], C[5001][201];
int H, W, Q;
int fdi[201][201];
void f(int du[][201], int dd[][201], int dp[][201], int m) {
for(int i = 1, r, ri; i <= W; i++) {
r = INF;
for(int j = 1, t; j <= W; j++) {
t = du[i][j] + B[m][j] + dd[j][i];
if(t < r) { r = t; ri = j; }
}
dp[i][i] = r; fdi[i][i] = ri;
}
for(int q = 1; q < W; q++) {
for(int s = 1, e = q+1, r, ri, rie; e <= W; s++, e++) {
r = INF; rie = fdi[s+1][e];
for(int j = fdi[s][e-1], t; j <= rie; j++) {
t = du[s][j] + B[m][j] + dd[j][e];
if(t < r) { r = t; ri = j; }
}
dp[s][e] = r; fdi[s][e] = ri;
}
for(int s = q+1, e = 1, r, ri, rie; s <= W; s++, e++) {
r = INF; rie = fdi[s][e+1];
for(int j = fdi[s-1][e], t; j <= rie; j++) {
t = du[s][j] + B[m][j] + dd[j][e];
if(t < r) { r = t; ri = j; }
}
dp[s][e] = r; fdi[s][e] = ri;
}
}
}
int rdp[3][201][201];
void run(int dp[][201], int x) {
for(int i = 1; i <= W; i++) {
dp[i][i] = 0;
for(int j = i+1; j <= W; j++)
dp[i][j] = dp[j][i] = C[x][j]-C[x][i];
}
}
void run(int dp[][201], int s, int e) {
run(rdp[0], s);
for(int i = s+1; i <= e; i++) {
run(rdp[1], i);
f(rdp[0], rdp[1], rdp[2], i-1);
memcpy(rdp[0], rdp[2], 201*201*4);
}
memcpy(dp, rdp[0], 201*201*4);
}
struct NOD {
int dp[201][201];
NOD *pl = NULL, *pr = NULL;
void cal(int s, int e) {
if(e-s < 20) {
run(dp, s, e);
return;
}
int m = (s+e) >> 1;
pl = new NOD(); pr = new NOD();
pl -> cal(s, m); pr -> cal(m+1, e);
f(pl->dp, pr->dp, dp, m);
}
void upd(int s, int e, int x) {
if(e-s < 20) {
run(dp, s, e);
return;
}
int m = (s+e) >> 1;
if(x <= m) pl -> upd(s, m, x);
else pr -> upd(m+1, e, x);
f(pl->dp, pr->dp, dp, m);
}
} nod;
void init(int H, int W, int A[5000][200], int B[5000][200]) {
::H = H; ::W = W;
for(int i = 1; i <= H; i++) {
for(int j = 1; j < W; j++) {
int c = A[i-1][j-1];
::A[i][j] = c;
::C[i][j+1] = ::C[i][j] + c;
}
}
for(int i = 1; i < H; i++)
for(int j = 1; j <= W; j++)
::B[i][j] = B[i-1][j-1];
nod.cal(1, H);
}
void changeH(int a, int b, int c) {
a++; b++;
A[a][b] = c;
for(int i = 1; i < W; i++)
C[a][i+1] = C[a][i] + A[a][i];
nod.upd(1, H, a);
}
void changeV(int a, int b, int c) {
a++; b++;
B[a][b] = c;
nod.upd(1, H, a);
}
int escape(int a, int b) {
return nod.dp[a+1][b+1];
}
