#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
/* Use segment tree, each node all C * C answers of interval l...r.
For query, it can be answered in O(1) by querying the root, V1 and V2
To merge, done naively is O(C * C * C). However, observe that we can
apply Knuth's optimization to make it O(C * C): uf we root i, then j
is always increasing.
Also, O(R * C * C) memory is too large, thus we can decompose the grid into
blocks of a certain size, then build a segment tree of those blocks. To update
a block, just brute force it.
*/
int R, C;
int H[5005][205], V[5005][205];
const int BLOCK_SIZE = 20;
const int BLOCK_COUNT = (5005 / BLOCK_SIZE);
struct segment_tree {
struct node {
vector<vector<int>> paths;
node(bool upd = false, int block = 0) {
paths.assign(C, vector<int>(C, INF));
if (!upd) return;
for (int i = 0; i < C; i++) {
paths[i][i] = 0;
for (int k = block * BLOCK_SIZE; k < (block + 1) * BLOCK_SIZE; k++) {
if (k >= R) continue;
for (int j = 1; j < C; j++) {
paths[i][j] = min(paths[i][j], paths[i][j - 1] + H[k][j - 1]);
}
for (int j = C - 2; j >= 0; j--) {
paths[i][j] = min(paths[i][j], paths[i][j + 1] + H[k][j]);
}
for (int j = 0; j < C; j++) {
paths[i][j] += V[k][j];
}
}
}
}
node merge(node a, node b) {
node res;
vector<vector<int>> mid(C, vector<int>(C, 0));
for (int len = 0; len < C; len++) {
for (int i = 0; i + len < C; i++) {
int j = i + len;
res.paths[i][j] = INF;
if (len == 0) {
for (int k = 0; k < C; k++) {
if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
mid[i][j] = k;
res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
}
}
continue;
}
/* DP Knuth's optimization, computing paths for new interval */
int le = mid[i][j - 1], ri = mid[i + 1][j];
assert(le <= ri);
for (int k = le; k <= ri; k++) {
if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
mid[i][j] = k;
res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
}
}
}
}
/* Now in reverse, to handle case i > j */
for (int len = 0; len < C; len++) {
for (int i = C - 1; i - len >= 0; i--) {
int j = i - len;
res.paths[i][j] = INF;
if (len == 0) {
for (int k = 0; k < C; k++) {
if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
mid[i][j] = k;
res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
}
}
continue;
}
/* DP Knuth's optimization, computing paths for new interval */
int le = mid[i][j + 1], ri = mid[i - 1][j];
for (int k = le; k >= ri; k--) {
if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
mid[i][j] = k;
res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
}
}
}
}
return res;
}
};
vector<node> tree;
inline int query(int v1, int v2) {
return tree[1].paths[v1][v2];
}
void update(int n, int tl, int tr, int p) {
if (tl == tr) {
tree[n] = node(true, tl);
return;
}
int mid = (tl + tr) / 2;
if (p <= mid)
update(n * 2, tl, mid, p);
else
update(n * 2 + 1, mid + 1, tr, p);
tree[n] = tree[n].merge(tree[n * 2], tree[n * 2 + 1]);
}
void build(int n, int tl, int tr) {
if (tl == tr) {
tree[n] = node(true, tl);
return;
}
int mid = (tl + tr) / 2;
build(n * 2, tl, mid), build(n * 2 + 1, mid + 1, tr);
tree[n] = tree[n].merge(tree[n * 2], tree[n * 2 + 1]);
}
void init() {
tree.clear();
tree.resize(4 * BLOCK_COUNT);
build(1, 0, BLOCK_COUNT - 1);
}
} seg;
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];
}
}
seg.init();
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
seg.update(1, 0, BLOCK_COUNT - 1, P / BLOCK_SIZE);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
seg.update(1, 0, BLOCK_COUNT - 1, P / BLOCK_SIZE);
}
int escape(int V1, int V2) {
return seg.query(V1, V2);
}
