#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 202
#include "wombats.h"
using namespace std;
int n,m,H[5001][202],V[5001][202],i,j;
const ll len=15;
struct Block
{
int l,r,dis[N][N];
void solve(int y1,Block &a,Block &b,int l,int r,int u,int v)
{
if(l>r) return ;
int mid=(l+r)>>1,pos;
dis[y1][mid]=2e9;
for(int i=u;i<=v;i++)
{
int k=V[a.r][i];
if(dis[y1][mid]>a.dis[y1][i]+b.dis[i][mid]+k)
{
dis[y1][mid]=a.dis[y1][i]+b.dis[i][mid]+k;
pos=i;
}
}
solve(y1,a,b,l,mid-1,u,pos);
solve(y1,a,b,mid+1,r,pos,v);
}
void comp(Block &a,Block &b)
{
for(int i=1;i<=m;i++) solve(i,a,b,1,m,1,m);
}
} ;
Block operator + (Block a,Block b)
{
Block res; res.l=a.l; res.r=b.r;
res.comp(a,b);
return res;
}
Block Cal_Row(int x)
{
Block res; res.l=res.r=x;
for(int y1=1;y1<=m;y1++)
{
res.dis[y1][y1]=0;
for(int y2=y1+1;y2<=m;y2++)
res.dis[y1][y2]=res.dis[y2][y1]=res.dis[y1][y2-1]+H[x][y2-1];
}
return res;
}
Block Recal(int l,int r)
{
Block res;
res=Cal_Row(l);
for(int i=l+1;i<=r;i++) res=res+Cal_Row(i);
return res;
}
struct Interval_Tree
{
Block st[1024];
void build(int id,int l,int r)
{
if(r-l+1<=15) { st[id]=Recal(l,r); return ; }
int mid=(l+r)>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
void update(int id,int l,int r,int u)
{
if(u<l || u>r) return ;
if(r-l+1<=15) { st[id]=Recal(l,r); return ; }
int mid=(l+r)>>1;
update(id*2,l,mid,u); update(id*2+1,mid+1,r,u);
st[id]=st[id*2]+st[id*2+1];
}
} IT;
void Change_H(int x,int y,int k)
{
H[x][y]=k;
IT.update(1,1,n,x);
}
void Change_V(int x,int y,int k)
{
V[x][y]=k;
IT.update(1,1,n,x);
}
int Ans(int y1,int y2) { return IT.st[1].dis[y1][y2]; }
void Take_information(int _n,int _m,int _H[5000][200],int _V[5000][200])
{
n=_n; m=_m;
for(i=1;i<=n;i++)
for(j=1;j<m;j++) H[i][j]=_H[i-1][j-1];
for(i=1;i<n;i++)
for(j=1;j<=m;j++) V[i][j]=_V[i-1][j-1];
IT.build(1,1,n);
}
///////////////////////////////////////////////////////////////////////////////////
void init(int R,int C,int _H[5000][200],int _V[5000][200]) { Take_information(R,C,_H,_V); }
void changeH(int P,int Q,int W) { Change_H(P+1,Q+1,W); }
void changeV(int P,int Q,int W) { Change_V(P+1,Q+1,W); }
int escape(int V1,int V2) { return Ans(V1+1,V2+1); }
/*
int main()
{
freopen("wombats.inp","r",stdin);
freopen("wombats.out","w",stdout);
int n,m,i,j,H[202][200],V[202][200];
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m-1;j++) cin>>H[i][j];
for(i=0;i<n-1;i++)
for(j=0;j<m;j++) cin>>V[i][j];
init(n,m,H,V);
int type;
while(cin>>type)
{
if(type==1)
{
int P,Q,W;
cin>>P>>Q>>W;
changeH(P,Q,W);
}
else if(type==2)
{
int P,Q,W;
cin>>P>>Q>>W;
changeV(P,Q,W);
}
else
{
int V1,V2;
cin>>V1>>V2;
cout<<escape(V1,V2)<<'\n';
}
}
}
*/
