#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int R = 5120, C = 205, B = 10, V = 512, inf = 1e9 + 5;
//const int R = 4, C = 4, B = 1, V = 4, inf = 1e9 + 5;
int h[R][C], v[R][C], st[V*2][C][C], l[V*2], r[V*2], o[C+1];
void print(string s, int m[C][C])
{
cout << s << "\n";
for (int i = 0; i < C; i++) for (int j = 0; j < C; j++) cout << m[i][j] << " \n"[j==C-1];
cout << "\n";
}
void upd(int &a, const int &b) { a = min(a, b); }
void update(int li, int ri, int vr = 0)
{
if (ri < l[vr] || li > r[vr]) return; // tento update sa ma netyka
if (l[vr] == r[vr]) // dosli sme na list
{
for (int i = 0; i < C; i++) for (int j = 0; j < C; j++) st[vr][i][j] = inf;
for (int c1 = 0; c1 < C; c1++)
{
st[vr][c1][c1] = 0;
for (int i = l[vr] * B; i < (r[vr] + 1) * B; i++)
{
for (int c2 = 0; c2 < C - 1; c2++) upd(st[vr][c1][c2 + 1], st[vr][c1][c2] + h[i][c2]);
for (int c2 = C - 1; c2 > 0; c2--) upd(st[vr][c1][c2 - 1], st[vr][c1][c2] + h[i][c2 - 1]);
for (int c2 = 0; c2 < C; c2++) st[vr][c1][c2] += v[i][c2];
}
}
//print("leaf " + to_string(vr) + ":", st[vr]);
return;
}
update(li, ri, vr * 2 + 1), update(li, ri, vr * 2 + 2);
fill(o, o + C, 0); o[C] = C - 1;
for (int c1 = 0; c1 < C; c1++) for (int c2 = C - 1; c2 >= 0; c2--)
{
pair<int, int> best(inf, -o[c2]); // kde sme nasli minimalnu hodnotu a jej index
for (int k = o[c2]; k <= o[c2 + 1]; k++)
best = min(best, {st[vr*2+1][c1][k]+st[vr*2+2][k][c2], -k});
st[vr][c1][c2] = best.first;
o[c2] = -best.second;
}
//print("non-leaf " + to_string(vr) + ":", st[vr]);
}
void init(int ri, int ci, int h[5000][200], int v[5000][200]) {
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) ::h[i][j] = inf;
for (int i = V - 1; i < V * 2; i++) l[i] = r[i] = i - (V - 1);
for (int i = V - 2; i >= 0; i--) l[i] = l[i*2+1], r[i] = r[i*2+2];
for (int i = 0; i < ri; i++) for (int j = 0; j < ci - 1; j++) ::h[i][j] = h[i][j];
for (int i = 0; i < ri - 1; i++) for (int j = 0; j < ci; j++) ::v[i][j] = v[i][j];
update(0, V - 1);
}
void changeH(int i, int j, int val) {
h[i][j] = val;
update(i/B, i/B);
}
void changeV(int i, int j, int val) {
v[i][j] = val;
update(i/B, i/B);
}
int escape(int v1, int v2) {
return st[0][v1][v2];
}
