#include "wombats.h"
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
using namespace std;
using vi = vector<int>;
const int rmx = 5000;
const int cmx = 200;
const int leaflim = 10;
int R, C;
int H[rmx][cmx], V[rmx][cmx];
const int INF = 2'000'000'001;
struct info
{
int r1, r2;
int a[cmx][cmx];
info()
{
;
}
};
info combine(info A, info B)
{
// cerr << "combine called\n";
info res;
vi old_barriers(C+2);
vi new_barriers(C+2);
old_barriers[0] = 0;
old_barriers[1] = C-1;
// cerr << "C = " << C << '\n';
for(int vmu = C-1; vmu >= 0; vmu--)
{
new_barriers[0] = 0;
int mxid;
// cerr << "\n\n\n";
// cerr << "vmu = " << vmu << '\n';
for(int v = max(vmu, 0); v <= C-1 && v-vmu <= C-1; v++)
{
int u = v-vmu;
// cerr << u << ' ' << v << '\n';
res.a[u][v] = INF;
int id = v - max(vmu, 0);
for(int i = old_barriers[id]; i <= old_barriers[id+1]; i++)
{
int currcost = A.a[u][i] + V[A.r2][i] + B.a[i][v];
if(currcost < res.a[u][v])
{
res.a[u][v] = currcost;
new_barriers[id+1] = i;
// cerr << "new barrier = " << i << '\n';
}
}
mxid = id;
}
// cerr << "old barriers = ";
// for(int z = 0; z <= mxid+1; z++)
// cerr << old_barriers[z] << ' ';
// cerr << '\n';
new_barriers[mxid+1 + 1] = C-1;
old_barriers = new_barriers;
}
old_barriers[0] = 0;
old_barriers[1] = C-1;
for(int vmu = -(C-1); vmu < 0; vmu++)
{
new_barriers[0] = 0;
int mxid;
// cerr << "\n\n\n";
// cerr << "vmu = " << vmu << '\n';
for(int v = max(vmu, 0); v <= C-1 && v-vmu <= C-1; v++)
{
int u = v-vmu;
// cerr << u << ' ' << v << '\n';
res.a[u][v] = INF;
int id = v - max(vmu, 0);
for(int i = old_barriers[id]; i <= old_barriers[id+1]; i++)
{
int currcost = A.a[u][i] + V[A.r2][i] + B.a[i][v];
if(currcost < res.a[u][v])
{
res.a[u][v] = currcost;
new_barriers[id+1] = i;
// cerr << "new barrier = " << i << '\n';
}
}
mxid = id;
}
// cerr << "old barriers = ";
// for(int z = 0; z <= mxid+1; z++)
// cerr << old_barriers[z] << ' ';
// cerr << '\n';
new_barriers[mxid+1 + 1] = C-1;
old_barriers = new_barriers;
}
res.r1 = A.r1;
res.r2 = B.r2;
// cerr << "combine returned\n";
return res;
}
info getinfo(int i1, int i2)
{
// cerr << "getinfo " << i1 << ' ' << i2 << '\n';
if(i1 == i2)
{
info res;
res.r1 = i1;
res.r2 = i2;
for(int j1 = 0; j1 < C; j1++)
{
res.a[j1][j1] = 0;
for(int j2 = j1+1; j2 < C; j2++)
res.a[j1][j2] = res.a[j1][j2-1] + H[i1][j2-1];
for(int j2 = j1-1; j2 >= 0; j2--)
res.a[j1][j2] = res.a[j1][j2+1] + H[i1][j2];
}
// cerr << "return : " << i1 << '\n';
return res;
}
else
{
return combine(getinfo(i1, i2-1), getinfo(i2, i2));
}
}
struct segtree
{
info curr;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int X, int Y)
{
// cerr << "build " << X << ' ' << Y << '\n';
if(Y-X+1 <= leaflim)
{
curr = getinfo(X, Y);
}
else
{
int mid = (X+Y)/2;
left = new segtree(X, mid);
right = new segtree(mid+1, Y);
curr = combine(left->curr, right->curr);
}
}
void recompute(int I)
{
if(left == NULL)
curr = getinfo(curr.r1, curr.r2);
else
{
if(I <= (curr.r1+curr.r2)/2)
left->recompute(I);
else
right->recompute(I);
curr = combine(left->curr, right->curr);
}
}
};
segtree ST;
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; j++)
{
H[i][j] = H_[i][j];
V[i][j] = V_[i][j];
}
}
// cerr << "init called\n";
ST = segtree(0, R-1);
// cerr << "answers = \n";
// for(int j1 = 0; j1 < C; j1++)
// for(int j2 = 0; j2 < C; j2++)
// cerr << j1 << " -> " << j2 << " : " << ST.curr.a[j1][j2] << '\n';
}
void changeH(int P, int Q, int W)
{
H[P][Q] = W;
ST.recompute(P);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
ST.recompute(P);
ST.recompute(P+1);
}
int escape(int V1, int V2)
{
return ST.curr.a[V1][V2];
}
