#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxc = 205;
const int maxr = 5005;
const int group = 30;
const int inf = 1e9;
int segm[(1<<10)+42][maxc][maxc];
int h[maxr][maxc],v[maxr][maxc];
int r,c;
int curr[maxc][maxc],pref[maxc], opt[maxc][maxc], help[maxc][maxc];//,sums[maxc],sums2[maxc],temp[maxc],mins[maxc];
void build(int k)
{
int prev =k;
int i,j;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
curr[i][j] = 0;
int start = group*k,stop = min(r-1,group*(k+1));
for(j=0;j<c-1;j++)
{
pref[j+1] = pref[j]+h[start][j];
}
for(i=0;i<c;i++)
for(j=0;j<c;j++)
curr[i][j] = abs(pref[i]-pref[j]);
//cout<<"INITIAL"<<prev<<" ={"<<endl;
/*for(i=0;i<c;i++){
for(j=0;j<c;j++)
cout<<curr[i][j]<<" ";
cout<<endl;}
cout<<" }"<<endl;*/
/* for(int t = start; t<stop;t++)
{
cout<<v[t][0]<<endl;
}
cout<<"&&"<<endl;*/
for(int t=start+1; t<=stop;t++)
{
for(j=0;j<c-1;j++)
{
pref[j+1] = pref[j]+h[t][j];
}
for(i=0;i<c;i++)
for(j=0;j<c;j++)
{
help[i][j] = inf;
opt[i][j]= -1;
}
for(i=0;i<c;i++)
{
for(j=0;j<c;j++)
{
int w = curr[i][j] + v[t-1][j] + pref[j];
if(help[i][0]>w)
{
help[i][0] = w;
opt[i][0] = j;
}
}
for(j=0;j<c;j++)
{
int w = curr[i][j] + v[t-1][j] + pref[c-1]-pref[j];
if(help[i][c-1]>w)
{
help[i][c-1] = w;
opt[i][c-1] = j;
}
}
}
for(i=1;i<c-1;i++)opt[c][i] = c-1;
for(int diff = -c; diff<=c; diff++)
{//cout<<diff<<endl;
for(i=0;i<c;i++)
{
int k = i+diff;
if(k<=0||k>=c-1)continue;
if(opt[i][k]!=-1)continue;//cout<<" "<<i<<" "<<k<<":: "<<opt[i][k-1]<<" "<<opt[i+1][k]<<endl;
for(int p = opt[i][k-1]; p <= opt[i+1][k]; p++)
{
if(help[i][k]>curr[i][p]+v[t-1][p]+abs(pref[p]-pref[k]))
{
help[i][k]=curr[i][p]+v[t-1][p]+abs(pref[p]-pref[k]);
opt[i][k] = p;
}
}
}
}
for(i=0;i<c;i++)
for(j=0;j<c;j++)
curr[i][j]= help[i][j];
/*cout<<prev<<" <-> "<<t<<" ={"<<endl;
for(i=0;i<c;i++){
for(j=0;j<c;j++)
cout<<curr[i][j]<<" ";
cout<<endl;}*/
}
/*cout<<" }"<<endl;*/
/* cout<<prev<<" ={"<<endl;
for(i=0;i<c;i++){
for(j=0;j<c;j++)
cout<<curr[i][j]<<" ";
cout<<endl;}
cout<<" }"<<endl;*/
}
void update(int v, int l, int r, int d)
{ int i,j;
//cout<<v<<" : "<<l<<" "<<r<<" "<<d<<endl;
if(l==r)
{
for(i=0;i<c;i++)
for(j=0;j<c;j++)
segm[v][i][j]= curr[i][j];
return ;
}
int mid = (l+r)/2;
if(d<=mid)
update(2*v,l,mid,d);
else
update(2*v+1,mid+1,r,d);
memset(opt,-1,sizeof(opt));
for(i=0;i<c;i++)
{
for(j=0;j<c;j++)
{
int cur = segm[2*v][i][j] + segm[2*v+1][j][0]+::v[mid][j];
if(opt[i][0]==-1||help[i][0]>cur)
{
help[i][0] = cur;
opt[i][0] = j;
}
cur = segm[2*v][i][j] + segm[2*v+1][j][c-1]+::v[mid][j];
if(opt[i][c-1]==-1||help[i][c-1]>cur)
{
help[i][c-1] = cur;
opt[i][c-1] = j;
}
}
}
for(i=0;i<c;i++)
{
opt[c][i] = c-1;
}
for(int diff=-c; diff<=c; diff++)
{
for(i=0;i<c;i++)
{
int k = i+diff;
if(k<=0||k>=c-1)continue;
if(opt[i][k]!=-1)continue;
help[i][k] = inf;
// cout<<v<<" :: "<<l<<" "<<r<<" "<<i<<" "<<k<<" "<<opt[i][k-1]<<" "<<opt[i+1][k]<<endl;
for(j=opt[i][k-1];j<=opt[i+1][k];j++)
{
int cur = segm[2*v][i][j] + segm[2*v+1][j][k]+::v[mid][j];
if(help[i][k]>cur)
{
help[i][k] = cur;
opt[i][k] = j;
}
}
}
}
for(i=0;i<c;i++)
for(j=0;j<c;j++)
segm[v][i][j] = help[i][j];
}
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<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];
for(i=0;i*group<r;i++)
{
//cout<<i<<endl;
build(i);
// cout<<i<<endl;
update(1,0,(r-1)/group,i);
//cout<<i<<endl;
}
}
void changeH(int P, int Q, int W) {
/* ... */
h[P][Q] = W;
build(P/group);
update(1,0,(r-1)/group,P/group);
}
void changeV(int P, int Q, int W) {
/* ... */
v[P][Q] = W;
build(P/group);
update(1,0,(r-1)/group,P/group);
}
int escape(int V1, int V2) {
// cout<<V1<<"-"<<V2<<endl;
return segm[1][V1][V2];
}
