#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9, SQRT = 5;
int R, C, n, H[5000][200], V[5000][200], ps[5000][200];
struct Node {
int agg[200][200];
Node *lc, *rc;
void pull(int i) {
for (int r = i * SQRT; r <= min((i + 1) * SQRT, R - 1); ++r) {
for (int c = 0; ++c < C;) ps[r][c] = ps[r][c - 1] + H[r][c - 1];
}
memset(agg, 0x3f, sizeof agg);
int dp[C];
for (int c1 = C; c1--;) {
agg[c1][c1] = 0;
for (int r = i * SQRT; r <= min((i + 1) * SQRT, R - 1); ++r) {
if (r > i * SQRT) {
for (int c2 = C; c2--;) agg[c1][c2] += V[r - 1][c2];
}
for (int c2 = C; --c2;) agg[c1][c2 - 1] = min(agg[c1][c2 - 1], agg[c1][c2] + H[r][c2 - 1]);
for (int c2 = 0; ++c2 < C;) agg[c1][c2] = min(agg[c1][c2], agg[c1][c2 - 1] + H[r][c2 - 1]);
}
}
}
void pull() {
int opt[C][C]{};
for (int i = C; i--;) {
int *o = &opt[i][i];
for (int j = 0; ++j < C;) {
if (lc->agg[i][j] + rc->agg[j][i] < lc->agg[i][*o] + rc->agg[*o][i]) *o = j;
}
agg[i][i] = lc->agg[i][*o] + rc->agg[*o][i];
for (int j = i; ++j < C;) {
o = &opt[i][j];
for (int k = *o = opt[i][j - 1]; ++k <= opt[i + 1][j];) {
if (lc->agg[i][k] + rc->agg[k][j] < lc->agg[i][*o] + rc->agg[*o][j]) *o = k;
}
agg[i][j] = lc->agg[i][*o] + rc->agg[*o][j];
o = &opt[j][i];
for (int k = *o = opt[j - 1][i]; ++k <= opt[j][i + 1];) {
if (lc->agg[j][k] + rc->agg[k][i] < lc->agg[j][*o] + rc->agg[*o][i]) *o = k;
}
agg[j][i] = lc->agg[j][*o] + rc->agg[*o][i];
}
}
}
Node(int l, int r) {
if (l < r) {
int m = (l + r) >> 1;
lc = new Node{l, m};
rc = new Node{m + 1, r};
pull();
} else pull(l);
}
void upd(int i, int l, int r) {
if (l == r) {
pull(l);
return;
}
int m = (l + r) >> 1;
if (i <= m) lc->upd(i, l, m);
else rc->upd(i, m + 1, r);
pull();
}
} *root;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = ((::R = R) - 2) / SQRT, ::C = C;
memcpy(::H, H, sizeof ::H);
memcpy(::V, V, sizeof ::V);
root = new Node{0, n};
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
if (P) root->upd((P - 1) / SQRT, 0, n);
if (P % SQRT == 0 and P < R) root->upd(P / SQRT, 0, n);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
root->upd(P / SQRT, 0, n);
}
int escape(int V1, int V2) { return root->agg[V1][V2]; }
