#include "wombats.h"
#include <algorithm>
#define R 5000
#define C 200
#define INF 1000000000
using namespace std;
struct Node{
int d[C][C];
Node *chi[2];
} *rt;
int r,c;
int h[R][C],v[R][C];
void dp(int d[C][C],int s,int e){
int i,j,k;
for(k=0;k<c;k++){
for(j=0;j<c;j++) d[k][j]=(k==j ? 0 : INF+1);
for(i=s;i<e;i++){
for(j=1;j<c;j++) d[k][j]=min(d[k][j],d[k][j-1]+h[i][j-1]);
for(j=c-2;j>=0;j--) d[k][j]=min(d[k][j],d[k][j+1]+h[i][j]);
for(j=0;j<c;j++) d[k][j]+=v[i][j];
}
for(j=1;j<c;j++) d[k][j]=min(d[k][j],d[k][j-1]+h[i][j-1]);
for(j=c-2;j>=0;j--) d[k][j]=min(d[k][j],d[k][j+1]+h[i][j]);
}
}
void mgDynamic(Node *no,int mid){
int i,j,k,t=0;
int l[2][C+1];
l[0][0]=0;
l[0][1]=c-1;
for(i=-(c-1);i<0;i++){
l[!t][0]=0;
for(j=-i;j<c;j++){
int p;
p=k=l[t][j+i];
no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
for(k=l[t][j+i]+1;k<=l[t][j+i+1];k++){
if(no->d[j][j+i]>no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k]){
p=k;
no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
}
}
l[!t][j+i+1]=p;
}
l[!t][i+c+1]=c-1;
t=!t;
}
for(i=0;i<c;i++){
for(j=0;j<c-i;j++){
int p;
p=k=l[t][j+i];
no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
for(k=l[t][j+i]+1;k<=l[t][j+i+1];k++){
if(no->d[j][j+i]>no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k]){
p=k;
no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
}
}
l[!t][j+i+1]=p;
}
t=!t;
}
}
void setTree(int s,int e,Node *no){
if(s+16>=e){
dp(no->d,s,e);
return;
}
int mid=(s+e)/2;
if(!no->chi[0]) no->chi[0]=new Node();
if(!no->chi[1]) no->chi[1]=new Node();
setTree(s,mid,no->chi[0]);
setTree(mid+1,e,no->chi[1]);
mgDynamic(no,mid);
}
void updateTree(int s,int e,int x,Node *no){
if(e<x || x<s) return;
if(s+16>=e){
dp(no->d,s,e);
return;
}
int mid=(s+e)/2;
updateTree(s,mid,x,no->chi[0]);
updateTree(mid+1,e,x,no->chi[1]);
mgDynamic(no,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<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];
rt=new Node();
setTree(0,r-1,rt);
}
void changeH(int P, int Q, int W) {
h[P][Q]=W;
updateTree(0,r-1,P,rt);
}
void changeV(int P, int Q, int W) {
v[P][Q]=W;
updateTree(0,r-1,P,rt);
}
int escape(int V1, int V2) {
return rt->d[V1][V2];
}
