#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 = 5001, maxc = 201;
vector<vector<int> > h(maxr, vector<int> (maxc, 0)), 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];
}
}
};
void merge(node l, node r, node &res)
{
if (l.l > r.l) swap(l, r);
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]);
}
node n;
int escape(int y1, int y2) {
return n.dp[y1][y2];
}
void changeH(int x, int y, int w) {
}
void changeV(int x, int y, int w) {
}
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 + 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];
n = node(0);
for (int i = 1; i < r; i++)
{
merge(n, node(i), n);
}
}
