#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
using pi = pair<int, pair<int, int>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int oo = 1000 * 1000 * 1000 + 7;
int R = 5000, C = 200, N = 500, batch = 10;
int H[5000][200], V[5000][200], ST[1024][200][200], O[201];
void update(int v, int lf, int rf, int lo, int hi) {
if(lf > hi || rf < lo) return;
if(lf == rf) {
for(int l = 0; l < C; l++)
for(int i = 0; i < C; i++)
ST[v][l][i] = oo;
for(int l = 0; l < C; l++) {
ST[v][l][l] = 0;
for(int i = lf * batch; i < (lf + 1) * batch; i++) {
for(int j = 1; j < C; j++)
ST[v][l][j] = min(ST[v][l][j], ST[v][l][j - 1] + H[i][j - 1]);
for(int j = C - 1; j > 0; j--)
ST[v][l][j - 1] = min(ST[v][l][j - 1], ST[v][l][j] + H[i][j - 1]);
for(int j = 0; j < C; j++)
ST[v][l][j] += V[i][j];
}
}
return;
}
int md = (lf + rf) / 2;
update(v * 2, lf, md, lo, hi);
update(v * 2 + 1, md + 1, rf, lo, hi);
for(int l = 0; l < C; l++) O[l] = 0;
for(int l = 0; l < C; l++) {
for(int i = C - 1; i >= 0; i--) {
pair<int, int> best = {oo, 0};
for(int j = O[i]; j <= O[i + 1]; j++)
best = min(best, {ST[v * 2][l][j] + ST[v * 2 + 1][j][i], -j});
ST[v][l][i] = best.first;
O[i] = -best.second;
}
}
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
for(int l = 0; l < R; l++)
for(int i = 0; i < C; i++)
H[l][i] = oo;
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];
O[C] = C - 1;
update(1, 0, N - 1, 0, N - 1);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
update(1, 0, N - 1, P / batch, P / batch);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
update(1, 0, N - 1, P / batch, P / batch);
}
int escape(int V1, int V2) {
return ST[1][V1][V2];
}
