#include<bits/stdc++.h>
#include"wombats.h"
using namespace std;
const int rmax=5e3+5,cmax=2e2+5,block_size=10,inf=1e9;
int r,c,h[rmax][cmax],v[rmax][cmax];
int tree[(1<<10)+42][cmax][cmax];
int current[cmax][cmax],help[cmax][cmax];
int pref[cmax];
int opt[cmax][cmax];
void brute_one(int i,int j,int k)
{
for(int p=0;p<c;p++)
{
int cur=current[j][p];
cur=cur+abs(pref[p]-pref[k]);
cur+=v[i-1][p];
if(help[j][k]>cur)
{
help[j][k]=cur;
opt[j][k]=p;
}
}
//cout<<"brute_one "<<j<<" "<<k<<" "<<opt[j][k]<<endl;
}
void make_block(int which)
{
for(int j=0;j<c;j++)
for(int k=0;k<c;k++)
if(j==k)current[j][k]=0;
else current[j][k]=inf;
int start=which*block_size,stop=min(r-1,which*block_size+block_size-1);
for(int i=start;i<=stop;i++)
{
for(int j=0;j<c;j++)
for(int k=0;k<c;k++)
help[j][k]=inf;
for(int j=0;j<c;j++)
pref[j+1]=pref[j]+h[i][j];
if(i==start)
{
for(int k=0;k<c;k++)
for(int p=0;p<c;p++)
help[k][p]=abs(pref[p]-pref[k]);
}
else
{
/*
for(int j=0;j<c;j++)
for(int k=0;k<c;k++)
for(int p=0;p<c;p++)
{
int cur=current[j][p];
cur=cur+abs(pref[p]-pref[k]);
cur+=v[i-1][p];
help[j][k]=min(help[j][k],cur);
}
*/
memset(opt,-1,sizeof(opt));
/*
for(int j=0;j<c;j++)
for(int k=0;k<c;k++)
brute_one(i,j,k);
*/
for(int t=0;t<c;t++)
{
brute_one(i,t,0);
brute_one(i,c-1,t);
}
for(int diff=-c;diff<=c;diff++)
{
for(int j=0;j<c;j++)
{
int k=j+diff;
if(0<=k&&k<c&&opt[j][k]==-1)
{
//cout<<j<<" "<<k<<endl;
assert(opt[j][k-1]!=-1&&opt[j+1][k]!=-1);
help[j][k]=inf;
for(int p=opt[j][k-1];p<=opt[j+1][k];p++)
{
int cur=current[j][p];
cur=cur+abs(pref[p]-pref[k]);
cur+=v[i-1][p];
if(help[j][k]>cur)
{
help[j][k]=cur;
opt[j][k]=p;
}
}
}
}
}
}
for(int j=0;j<c;j++)
for(int k=0;k<c;k++)
current[j][k]=help[j][k];
/*
cout<<start<<" "<<i<<endl;
for(int j=0;j<c;j++)
{
for(int k=0;k<c;k++)cout<<current[j][k]<<" ";
cout<<endl;
}
cout<<"---"<<endl;
*/
}
}
void brute(int node,int j,int k,int av)
{
tree[node][j][k]=inf;
for(int p=0;p<c;p++)
{
int cur=tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k];
//cout<<"cur= "<<cur<<endl;
if(tree[node][j][k]>cur)
{
tree[node][j][k]=cur;
opt[j][k]=p;
}
}
//cout<<"brute "<<j<<" "<<k<<" "<<opt[j][k]<<endl;
}
void build(int node,int l,int r,int pos)
{
if(l==r)
{
for(int j=0;j<c;j++)
for(int k=0;k<c;k++)
tree[node][j][k]=current[j][k];
return;
}
int av=(l+r)/2;
if(pos<=av)build(node*2,l,av,pos);
else build(node*2+1,av+1,r,pos);
//opt[i][j-1]<=opt[i][j]<=opt[i+1][j]
/*
for(int j=0;j<c;j++)
for(int k=0;k<c;k++)
{
tree[node][j][k]=inf;
for(int p=0;p<c;p++)
tree[node][j][k]=min(tree[node][j][k],tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k]);
}
*/
memset(opt,-1,sizeof(opt));
for(int i=0;i<c;i++)
{
brute(node,i,0,av);
brute(node,c-1,i,av);
}
for(int diff=-c;diff<=c;diff++)
{
for(int j=0;j<c;j++)
{
int k=j+diff;
if(0<=k&&k<c&&opt[j][k]==-1)
{
//cout<<j<<" "<<k<<endl;
assert(opt[j][k-1]!=-1&&opt[j+1][k]!=-1);
tree[node][j][k]=inf;
for(int p=opt[j][k-1];p<=opt[j+1][k];p++)
{
int cur=tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k];
if(tree[node][j][k]>cur)
{
tree[node][j][k]=cur;
opt[j][k]=p;
}
}
}
}
}
}
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]=H[i][j];
for(int i=0;i<R-1;i++)
for(int j=0;j<C;j++)
v[i][j]=V[i][j];
for(int i=0;i*block_size<r;i++)
{
make_block(i);
build(1,0,(r-1)/block_size,i);
}
}
void changeH(int P,int Q,int W)
{
h[P][Q]=W;
make_block(P/block_size);
build(1,0,(r-1)/block_size,P/block_size);
}
void changeV(int P,int Q,int W)
{
v[P][Q]=W;
make_block(P/block_size);
build(1,0,(r-1)/block_size,P/block_size);
}
int escape(int V1,int V2)
{
return tree[1][V1][V2];
}
