#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include "wombats.h"
typedef long long ll;
using namespace std;
int r, c; const int inf = 1e9 + 79, maxr = 10001, maxc = 201;
int r2 = 1;
vector<vector<int> > h(maxr, vector<int>(maxc, inf)), v(maxr, vector<int>(maxc, 0)); // h -> cesta z predosleho stlpca, v -> cesta z predosleho riadku
class node
{
public:
int l, r;
vector<vector<int> > dp;
node() : dp(vector<vector<int> >(c, vector<int>(c, 0))) {}
node(int rw) : dp(vector<vector<int> >(c, vector<int>(c, 0))), l(rw), r(rw) {
for (int i = 0; i < c; i++) for (int j = 0; j < c; j++) {
dp[i][j] = v[rw][i];
for (int k = min(i, j) + 1; k <= max(i, j); k++) dp[i][j] += h[rw][k], dp[i][j] = min(dp[i][j], inf);
}
}
};
void merge(const node &l, const node &r, node& res)
{
res.l = l.l, res.r = r.r;
for (int i = 0; i < c; i++) for (int j = 0; j < c; j++) res.dp[i][j] = inf;
for (int i = 0; i < c; i++) for (int j = 0; j < c; j++) for (int k = 0; k < c; k++)
res.dp[i][j] = min(res.dp[i][j], l.dp[i][k] + r.dp[k][j]);
}
vector<node> st; // musi to byt presne r aby sme vedeli skoncit v y2
void update(int i)
{
st[i + r2] = node(i); i += r2;
for (i = (i >> 1); i > 0; i >>= 1)
merge(st[(i << 1)], st[(i << 1) | 1], st[i]);
}
int escape(int y1, int y2) {
return st[1].dp[y1][y2];
}
void changeH(int x, int y, int w) {
h[x][y + 1] = w;
update(x);
}
void changeV(int x, int y, int w) {
v[x + 1][y] = w;
update(x + 1);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R, c = C;
while (r2 < r) r2 <<= 1;
st.resize(r2 * 2);
for (int i = 0; i < r; i++) for (int j = 0; j < c - 1; j++)
h[i][j + 1] = H[i][j];
for (int i = 0; i < r - 1; i++) for (int j = 0; j < c; j++)
v[i + 1][j] = V[i][j];
for (int i = 0; i < r2; i++) st[i + r2] = node(i);
for (int i = r2 - 1; i > 0; i--) merge(st[i << 1], st[(i << 1) | 1], st[i]);
}
