#include "wombats.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int ROW = 5002, COL = 202, B = 10;
int INF = 2e9;
int h[ROW][COL], v[ROW][COL],C,R;
struct node {
ll d[COL][COL];
} tree[4 * ROW / 10];
node merge(node a, node b, int mid) {
node c = a;
vector<vector<int> > opt;
opt.resize(C, vector<int>(C ));
for(int i = 0; i < C; i++) {
for(int j = 0; j < C; j++) {
a.d[i][j] += v[mid][j];
}
}
for(int i = 0; i < C; i++) {
c.d[i][i] = INF;
for(int j = 0; j < C; j++) {
if(c.d[i][i] >= a.d[i][j] + b.d[j][i]) {
opt[i][i] = j;
c.d[i][i]= a.d[i][j] + b.d[j][i];
}
}
}
for(int X = 1; X < C; X++) {
// i x j
for(int i = 0; i < C; i++) {
int j = i + X;
if(j < C) { c.d[i][j] = INF;
for(int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
if(c.d[i][j] >= a.d[i][k] + b.d[k][j]) {
c.d[i][j] = a.d[i][k] + b.d[k][j];
opt[i][j] = k;
}
}
}
j = i - X;
if(j >= 0) {
c.d[i][j] = INF;
for(int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
if(c.d[i][j] >= a.d[i][k] + b.d[k][j]) {
c.d[i][j] = a.d[i][k] + b.d[k][j];
opt[i][j] = k;
}
}
}
}
}
return c;
}
node get(int l, int r) {
if(l == r) {
node a;
for(int i = 0; i < C; i++) {
a.d[i][i] = 0;
for(int j = i + 1; j < C; j++) {
a.d[i][j] = a.d[i][j - 1] + h[l][j - 1];
}
for(int j = i - 1; j >= 0; j--) {
a.d[i][j] = a.d[i][j + 1] + h[l][j];
}
}
return a;
}
int mid = (l + r) / 2;
return merge(get(l, mid), get(mid + 1, r), mid);
}
void build(int u,int l, int r) {
if(r - l + 1 <= B) {
tree[u] = get(l, r);
return;
}
int mid = (l + r) / 2;
build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
tree[u] = merge(tree[2 * u], tree[2 * u + 1], mid);
}
void upd(int u,int id, int l, int r) {
if(l > id || r < id) return;
if(r - l + 1 <= B) {
tree[u] = get(l, r);
return;
}
int mid = (l + r) / 2;
upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
tree[u] = merge(tree[2 * u], tree[2 * u + 1], mid);
}
void init(int r, int c, int H[5000][200], int V[5000][200]) {
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];
}
R = r; C = c; --R;
build(1, 0, R);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
upd(1, P, 0, R);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
upd(1, P, 0, R);
}
int escape(int V1, int V2) {
return tree[1].d[V1][V2];
}
