#include "wombats.h"
#define SZ 64
#define INF 999999999
int D[128][201][201],bucket_sz,h[5010][210],v[5010][210],TP[100][210][210],r,c;
void Do(int num,int a)
{
int i,j,k,bsz=bucket_sz;
if(a+bsz>r)bsz=r-a;
for(i=0;i<=bsz;i++)
for(j=0;j<c;j++)
for(k=0;k<c;k++)
TP[i][j][k]=INF;
for(i=0;i<c;i++)TP[0][i][i]=0;
for(i=0;i<bsz;i++)
{
for(j=0;j<c;j++){
for(k=1;k<c;k++)
if(TP[i][j][k]>TP[i][j][k-1]+h[a+i][k-1])
TP[i][j][k]=TP[i][j][k-1]+h[a+i][k-1];
for(k=c-2;k>=0;k--)
if(TP[i][j][k]>TP[i][j][k+1]+h[a+i][k])
TP[i][j][k]=TP[i][j][k+1]+h[a+i][k];
}
for(j=0;j<c;j++)
for(k=0;k<c;k++)
TP[i+1][j][k]=TP[i][j][k]+v[a+i][k];
}
for(i=0;i<c;i++)
for(j=0;j<c;j++)
D[num][i][j]=TP[bsz][i][j];
}
void Update(int a)
{
int i,j,k,bsz=13,w[20],t;
int c1=a*2,c2=a*2+1;
for(i=0;i<c;i++)for(j=0;j<c;j++)D[a][i][j]=INF+1;
for(i=0;i<c;i++){
t=0;
for(j=0;j<c;j+=bsz){
for(k=0;k<c;k++)
if(D[a][i][j]>D[c1][i][k]+D[c2][k][j])
D[a][i][j]=D[c1][i][k]+D[c2][k][j],w[t]=k;
t++;
}
w[(c-1)/bsz+1]=c-1;
for(j=0;j<c;j++){
if(j%bsz==0)continue;
t=w[j/bsz+1];
for(k=w[j/bsz];k<=t;k++)
{
if(D[a][i][j]>D[c1][i][k]+D[c2][k][j])
D[a][i][j]=D[c1][i][k]+D[c2][k][j];
}
}
}
}
void changeV(int P, int Q, int W)
{
v[P][Q]=W;
int a=P/bucket_sz;
Do(SZ+a,a*bucket_sz);
a+=SZ;
while(a>1){
a>>=1;
Update(a);
}
}
void changeH(int P, int Q, int W)
{
h[P][Q]=W;
int a=P/bucket_sz;
Do(SZ+a,a*bucket_sz);
a+=SZ;
while(a>1){
a>>=1;
Update(a);
}
}
int escape(int V1, int V2)
{
return D[1][V1][V2];
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
r=R,c=C;
int i,j,k;
for(i=0;i<R;i++)for(j=0;j<C-1;j++)h[i][j]=H[i][j];
for(i=0;i<R-1;i++)for(j=0;j<C;j++)v[i][j]=V[i][j];
bucket_sz=(R-1)/64+1;
for(i=0;i<R;i+=bucket_sz)
{
Do(SZ+i/bucket_sz,i);
}
for(i=SZ+i/bucket_sz;i<128;i++){
for(j=0;j<C;j++){
for(k=0;k<C;k++)D[i][j][k]=INF;
D[i][j][j]=0;
}
}
for(i=SZ-1;i>=1;i--)Update(i);
}
