#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXR = 5000;
const int MAXC = 200;
const int INF = 987654321;
int R, C, H[MAXR+10][MAXC+10], V[MAXR+10][MAXC+10];
struct Node
{
vector<vector<int>> V;
Node() { V=vector<vector<int>>(C, vector<int>(C)); }
};
Node tree[MAXR*4+10];
int opt[MAXC+10][MAXC+10];
void add(Node &now, Node &lc, Node &rc, int pos)
{
int i, j, k, p;
now=Node();
for(k=-(C-1); k<=(C-1); k++)
{
for(i=max(0, k); i<min(C+k, C); i++)
{
j=i-k; int l, r;
if(i==0) l=0;
else l=opt[i-1][j];
if(j==C-1) r=C-1;
else r=opt[i][j+1];
int t=l; now.V[i][j]=INF;
for(p=l; p<=r; p++)
{
if(now.V[i][j]>lc.V[i][p]+rc.V[p][j]+V[pos][p])
{
t=p; now.V[i][j]=lc.V[i][p]+rc.V[p][j]+V[pos][p];
}
}
opt[i][j]=t;
}
}
}
void initnode(Node &now, int tl, int tr)
{
int i, j, k;
now=Node();
for(i=0; i<C; i++)
{
int s=0;
for(j=i+1; j<C; j++)
{
s+=H[tl][j-1];
now.V[i][j]=now.V[j][i]=s;
}
}
for(k=tl+1; k<=tr; k++)
{
Node p;
for(i=0; i<C; i++)
{
int s=0;
for(j=i+1; j<C; j++)
{
s+=H[k][j-1];
p.V[i][j]=p.V[j][i]=s;
}
}
Node t;
add(t, now, p, k-1);
now=t;
}
}
void init(int node, int tl, int tr)
{
if(tr-tl+1<=10)
{
initnode(tree[node], tl, tr);
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
add(tree[node], tree[node*2], tree[node*2+1], mid);
}
void init(int _R, int _C, int _H[5000][200], int _V[5000][200])
{
int i, j;
R=_R; C=_C;
for(i=0; i<R; i++) for(j=0; j+1<C; j++) H[i][j]=_H[i][j];
for(i=0; i+1<R; i++) for(j=0; j<C; j++) V[i][j]=_V[i][j];
init(1, 0, R-1);
}
void updateH(int node, int tl, int tr, int y)
{
if(tr-tl+1<=10)
{
initnode(tree[node], tl, tr);
return;
}
int mid=tl+tr>>1;
if(y<=mid) updateH(node*2, tl, mid, y);
else updateH(node*2+1, mid+1, tr, y);
add(tree[node], tree[node*2], tree[node*2+1], mid);
}
void updateV(int node, int tl, int tr, int y)
{
if(tr-tl+1<=10)
{
initnode(tree[node], tl, tr);
return;
}
int mid=tl+tr>>1;
if(y==mid) { add(tree[node], tree[node*2], tree[node*2+1], mid); return; }
if(y<=mid) updateV(node*2, tl, mid, y);
else updateV(node*2+1, mid+1, tr, y);
add(tree[node], tree[node*2], tree[node*2+1], mid);
}
void changeH(int P, int Q, int W)
{
H[P][Q]=W;
updateH(1, 0, R-1, P);
}
void changeV(int P, int Q, int W)
{
V[P][Q]=W;
updateV(1, 0, R-1, P);
}
int escape(int V1, int V2)
{
return tree[1].V[V1][V2];
}
