#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int SZ = 10;
int h[5001][201], v[5001][201];
int st[1024][201][201];
int r, c;
int opt[201];
void update(int id, int le, int ri, int L, int R){
if(ri < L || le > R) return;
if(le == ri){
memset(st[id], 0x3f, sizeof st[id]);
for(int i = 0; i < c; ++i){
st[id][i][i] = 0;
for(int k = le * SZ; k < min((le + 1) * SZ, r); ++k){
for(int j = 1; j < c; ++j)
st[id][i][j] = min(st[id][i][j], st[id][i][j - 1] + h[k][j - 1]);
for(int j = c - 2; j >= 0; --j)
st[id][i][j] = min(st[id][i][j], st[id][i][j + 1] + h[k][j]);
for(int j = 0; j < c; ++j)
st[id][i][j] += v[k][j];
}
}
return;
}
int m = (le + ri) >> 1;
update(id << 1, le, m, L, R);
update(id << 1 | 1, m + 1, ri, L, R);
memset(opt, 0, sizeof opt);
opt[c] = c - 1;
for(int i = 0; i < c; ++i){
for(int j = c - 1; j >= 0; --j){
pair<int, int> mn = {INT_MAX, 0};
for(int k = opt[j]; k <= opt[j + 1]; ++k)
mn = min(mn, {st[id << 1][i][k] + st[id << 1 | 1][k][j], -k});
opt[j] = -mn.second;
st[id][i][j] = mn.first;
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R; c = C;
for(int i = 0; i < R - 1; ++i)
for(int j = 0; j < C; ++j)
v[i][j] = V[i][j];
for(int i = 0; i < R; ++i)
for(int j = 0; j < C - 1; ++j)
h[i][j] = H[i][j];
update(1, 0, (r - 1) / SZ, 0, (r - 1) / SZ);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
update(1, 0, (r - 1) / SZ, P / SZ, P / SZ);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
update(1, 0, (r - 1) / SZ, P / SZ, P / SZ);
}
int escape(int V1, int V2) {
return st[1][V1][V2];
}
