#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MR = 5010;
const int MC = 210;
const int BL = 20;
const int CBL = 256;
const int Inf = 1000000000;
int r, c;
int H[MR][MC], V[MR][MC], ps[MC];
struct node {
int dp[MC][MC];
};
node seg[CBL << 1];
int opt[MC][MC];
void Merge(int A, int B, int C, int rw){
memset(seg[A].dp, 31, sizeof seg[A].dp);
int lc, rc, mn, nw, idx;
for(int i = 0; i < c; i++){
for(int j = c - 1; j >= 0; j--){
lc = (i ? opt[i - 1][j] : 0);
rc = (j == c - 1 ? c - 1 : opt[i][j + 1]);
mn = seg[C].dp[i][lc] + V[rw][lc] + seg[B].dp[lc][j];
idx = lc;
for(int k = lc + 1; k <= rc; k++){
nw = seg[C].dp[i][k] + V[rw][k] + seg[B].dp[k][j];
if(nw < mn){
mn = nw;
idx = k;
}
}
opt[i][j] = idx;
seg[A].dp[i][j] = mn;
}
}
}
int tdp[BL][MC];
void BuildRow(int id, int ur, int dr){
//cerr << "# " << ur << ' ' << dr << '\n';
int row;
for(int sc = 0; sc < c; sc ++){
memset(tdp, 0, sizeof tdp);
ps[0] = 0;
for(int i = 1; i < c; i++) ps[i] = ps[i - 1] + H[dr][i - 1];
for(int i = 0; i < c; i++) tdp[0][i] = abs(ps[i] - ps[sc]);
for(int i = dr - 1; i >= ur; i--){
row = dr - i;
ps[0] = 0;
for(int j = 1; j < c; j++) ps[j] = ps[j - 1] + H[i][j - 1];
int res = Inf;
for(int j = 0; j < c; j++){
res = min(res, V[i][j] + tdp[row - 1][j] - ps[j]);
tdp[row][j] = ps[j] + res;
}
res = Inf;
for(int j = c - 1; j >= 0; j--){
res = min(res, V[i][j] + tdp[row - 1][j] + ps[j]);
tdp[row][j] = min(tdp[row][j], res - ps[j]);
}
}
/*
for(int i = 0; i < c; i++)
for(int j = 0; j < c; j++)
seg[id].dp[i][j] = abs(ps[i] - ps[j]); //min(seg[id].dp[i][j]);
*/
for(int i = 0; i < c; i++)
seg[id].dp[sc][i] = tdp[dr - ur][i];
}
}
void Build(int id, int L, int R){
if(R - L <= BL){
BuildRow(id, L, R - 1);
return ;
}
int mid = (L + R) >> 1;
Build(id << 1, L, mid);
Build(id << 1 | 1, mid, R);
Merge(id, id << 1, id << 1 | 1, mid - 1);
}
void ReBuild(int id, int L, int R, int lq, int rq){
if(rq < L || R <= rq) return ;
if(lq < L || R <= lq) return ;
if(R - L <= BL){
BuildRow(id, L, R - 1);
return ;
}
int mid = (L + R) >> 1;
ReBuild(id << 1, L, mid, lq, rq);
ReBuild(id << 1 | 1, mid, R, lq, rq);
Merge(id, id << 1, id << 1 | 1, mid - 1);
}
/*
void Build(){
memset(dp, 0, sizeof dp);
//fill(dp[R - 1], dp[R - 1] + C, 0);
for(int i = R - 2; i >= 0; i--){
ps[0] = 0;
for(int j = 1; j < C; j++) ps[j] = ps[j - 1] + H[i][j - 1];
int res = Inf;
for(int j = 0; j < C; j++){
res = min(res, V[i][j] + dp[i + 1][j] - ps[j]);
dp[i][j] = ps[j] + res;
}
res = Inf;
for(int j = C - 1; j >= 0; j--){
res = min(res, V[i][j] + dp[i + 1][j] + ps[j]);
dp[i][j] = res - ps[j];
}
}
}
*/
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
/* ... */
r = _R; c = _C;
for(int i = 0; i < r; i++)
for(int j = 0; j < c - 1; j++)
H[i][j] = _H[i][j];
for(int i = 0; i < r - 1; i++)
for(int j = 0; j < c; j++)
V[i][j] = _V[i][j];
Build(1, 0, r);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
ReBuild(1, 0, r, P, P);
/* ... */
}
void changeV(int P, int Q, int W){
V[P][Q] = W;
ReBuild(1, 0, r, P, P + 1);
//Build(1, 0, r);
/* ... */
}
int escape(int V1, int V2) {
return seg[1].dp[V2][V1];
}
