#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int r, c;
int h[5000][200], v[5000][200];
int p[5000][200];
int T[2000][200][200];
int F[5000][200];
void buildToNode(int val, int tl, int tr) {
for(int col = 0; col < c; col++) {
for(int j = 0; j < c; j++) {
if(j <= col) F[0][j] = p[tl][col] - p[tl][j];
else F[0][j] = p[tl][j] - p[tl][col];
}
for(int i = tl + 1; i <= tr; i++) {
int mi = INF;
for(int j = 0; j < c; j++) {
mi = min(mi, F[i - tl - 1][j] - p[i][j] + v[i - 1][j]);
F[i - tl][j] = mi + p[i][j];
}
mi = INF;
for(int j = c - 1; j >= 0; j--) {
mi = min(mi, F[i - tl - 1][j] + p[i][j] + v[i - 1][j]);
F[i - tl][j] = min(F[i - tl][j], mi - p[i][j]);
}
}
for(int i = 0; i < c; i++) T[val][col][i] = F[tr - tl][i];
}
}
void merge(int val, int mid, int tl, int tr) {
for(int i = 0; i < c; i++) {
for(int j = 0; j < c; j++) {
T[val][i][j] = INF;
}
}
vector < int > dest(c);
for(int i = 0; i < c; i++) {
for(int k = 0; k < c; k++) {
if(T[2 * val + 1][i][k] + v[mid][k] + T[2 * val + 2][k][i] < T[val][i][i]) {
dest[i] = k;
T[val][i][i] = T[2 * val + 1][i][k] + v[mid][k] + T[2 * val + 2][k][i];
}
}
}
for(int d = -c; d <= c; d++) {
if(d == 0) continue;
for(int i = max(0, -d); i < min(c, c - d); i++) {
int L, R;
L = dest[min(i, i + d)];
R = dest[max(i, i + d)];
for(int k = L; k <= R; k++) {
T[val][i][i + d] = min(T[val][i][i + d], T[2 * val + 1][i][k] + v[mid][k] + T[2 * val + 2][k][i + d]);
}
}
}
/*
for(int i = 0; i < c; i++) {
for(int j = 0; j < c; j++) {
for(int k = 0; k < c; k++) T[val][i][j] = min(T[val][i][j], T[2 * val + 1][i][k] + v[mid][k] + T[2 * val + 2][k][j]);
}
}
*/
}
void build(int val, int tl, int tr) {
if(tr - tl + 1 <= 10) {
buildToNode(val, tl, tr);
return;
}
int tm = (tl + tr) >> 1;
build(2 * val + 1, tl, tm);
build(2 * val + 2, tm + 1, tr);
merge(val, tm, tl, tr);
}
void update(int val, int tl, int tr, int pos) {
if(tr - tl + 1 <= 10) {
buildToNode(val, tl, tr);
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) update(2 * val + 1, tl, tm, pos);
else update(2 * val + 2, tm + 1, tr, pos);
merge(val, tm, tl, tr);
}
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; j++) {
h[i][j] = H[i][j];
v[i][j] = V[i][j];
if(j >= 1) p[i][j] = p[i][j - 1] + h[i][j - 1];
else p[i][j] = 0;
}
}
build(0, 0, r - 1);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
for(int j = 0; j < c; j++) {
if(j >= 1) p[P][j] = p[P][j - 1] + h[P][j - 1];
else p[P][j] = 0;
}
update(0, 0, r - 1, P);
if(P != r - 1) update(0, 0, r - 1, P + 1);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
update(0, 0, r - 1, P);
if(P != r - 1) update(0, 0, r - 1, P + 1);
}
int escape(int v1, int v2) {
return T[0][v1][v2];
}
