#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
struct node{
int n,d[100][100];
void ini(int x){
n=x;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)d[i][j]=0;
else d[i][j]=INF;
}
}
}
node plus(node &q){
node res;
res.ini(n);
int a[100][100];
for(int i=n-1;i>-n;i--){
for(int j=max(-i,0);i+j<n&&j<n;j++){
int x,y;
if(j-1>=0)x=a[i+j][j-1];
else x=0;
if(i+j+1<n)y=a[i+j+1][j];
else y=n-1;
for(int k=x;k<=y;k++)if(d[i+j][k]+q.d[k][j]<d[i+j][x]+q.d[x][j])x=k;
a[i+j][j]=x;
res.d[i+j][j]=min(d[i+j][x]+q.d[x][j],INF);
}
}
return res;
}
};
struct SEG{
int n,k,id[1<<14];
node seg[10011];
void ini(int x){
n=x;
for(int i=0;i<1<<14;i++)id[i]=-1;
k=0;
for(int i=0;i<5000;i++){
int a=i+(1<<13)-1;
if(id[a]==-1)id[a]=k++;
while(a>0){
a=(a-1)/2;
if(id[a]==-1)id[a]=k++;
if(id[a*2+1]==-1)id[a*2+1]=k++;
if(id[a*2+2]==-1)id[a*2+2]=k++;
}
}
for(int i=0;i<k;i++)seg[i].ini(n);
}
void up(int a,node &q){
a+=(1<<13)-1;
seg[id[a]]=q;
while(a>0){
a=(a-1)/2;
seg[id[a]]=seg[id[a*2+1]].plus(seg[id[a*2+2]]);
}
}
int dis(int a,int b){
return seg[id[0]].d[a][b];
}
};
int h[5000][100],w[5000][100],n,m,p[100];
SEG s;
void change(int x){
p[0]=0;
for(int i=1;i<m;i++)p[i]=p[i-1]+h[x][i-1];
node res;
res.ini(m);
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
res.d[i][j]=p[max(i,j)]-p[min(i,j)]+w[x][j];
}
}
s.up(x,res);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n=R,m=C;
s.ini(m);
for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)h[i][j]=H[i][j];
for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)w[i][j]=V[i][j];
for(int i=0;i<n;i++)change(i);
}
void changeH(int a, int b, int x) {
h[a][b]=x;
change(a);
}
void changeV(int a, int b, int x) {
w[a][b]=x;
change(a);
}
int escape(int a, int b) {
return s.dis(a,b);
}
