#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#define INF 2000000000
const int B = 20;
int h[5000][200], v[5000][200], bl[5000], br[5000], pos[5000], r, c;
struct node {
int s, e, m;
vector<vector<int>> f;
node *l, *r;
node(int _s, int _e) {
s = _s, e = _e, m = (s+e)/2;
for(int i = 0; i < 200; i++) {
vector<int> v(200);
f.push_back(v);
}
if(s != e) {
l = new node(s, m);
r = new node(m+1, e);
merge(l->f, r->f, f);
} else {
build(s);
}
}
void build(int s) {
for(int i = 0; i < c; i++) {
for(int j = i, res = 0; j < c; j++, res += h[bl[s]][j-1]) f[i][j] = res;
for(int j = i, res = 0; j >= 0; j--, res += h[bl[s]][j]) f[i][j] = res;
for(int j = 0; j < c; j++) f[i][j] += v[bl[s]][j];
for(int k = bl[s]+1; k <= br[s]; k++) {
for(int j = 1; j < c; j++) f[i][j] = min(f[i][j], f[i][j-1] + h[k][j-1]);
for(int j = c-2; j >= 0; j--) f[i][j] = min(f[i][j], f[i][j+1] + h[k][j]);
for(int j = 0; j < c; j++) f[i][j] += v[k][j];
}
}
}
void merge(vector<vector<int>> &a, vector<vector<int>> &b, vector<vector<int>> &f) {
for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) f[i][j] = INF;
int p[c][c];
memset(p, -1, sizeof(p));
for(int i = 0; i < c; i++) {
for(int j = c-1; j >= 0; j--) {
int st = (i && p[i-1][j] != -1 ? p[i-1][j] : 0);
int ed = (j != c-1 && p[i][j+1] != -1 ? p[i][j+1] : c-1);
for(int k = st; k <= ed; k++) if(f[i][j] > a[i][k] + b[k][j]) {
f[i][j] = a[i][k] + b[k][j];
p[i][j] = k;
}
}
}
}
void update(int x) {
if(s == e) {build(s); return;}
else if(x > m) r->update(x);
else l->update(x);
merge(l->f, r->f, f);
}
} *root;
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];
int cnt = (r-1)/B + 1;
for(int i = 0; i < cnt; i++) {
bl[i] = i*B;
br[i] = min((i+1)*B-1, r-1);
}
for(int i = 0; i < cnt; i++) {
for(int j = bl[i]; j <= br[i]; j++) pos[j] = i;
}
root = new node(0, cnt-1);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
root->update(pos[P]);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
root->update(pos[P]);
}
int escape(int V1, int V2) {
return root->f[V1][V2];
}
