#include<bits/stdc++.h>
#include"wombats.h"
using namespace std;
const int rmax=5e3+5,cmax=2e2+5;
int r,c,h[rmax][cmax],v[rmax][cmax];
bool run=0;
int mem[cmax][cmax];
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];
run=1;
}
int in=0;
void changeH(int P,int Q,int W)
{
in=0;
h[P][Q]=W;
run=1;
}
void changeV(int P,int Q,int W)
{
in=0;
v[P][Q]=W;
run=1;
}
int dist[rmax][cmax];
priority_queue< pair<int,pair<int,int> > > pq,idle;
int dij(int x1,int y1)
{
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
dist[i][j]=-1;
pq=idle;
pq.push({0,{x1,y1}});
pair<int,pair<int,int> > p;
int d,x,y;
while(pq.size())
{
p=pq.top();
pq.pop();
d=-p.first;
x=p.second.first;
y=p.second.second;
//cout<<x<<" "<<y<<" -> "<<d<<endl;
if(dist[x][y]!=-1)continue;
dist[x][y]=d;
if(x!=r-1)pq.push({-(d+v[x][y]),{x+1,y}});
if(y)pq.push({-(d+h[x][y-1]),{x,y-1}});
if(y!=c-1)pq.push({-(d+h[x][y]),{x,y+1}});
}
for(int j=0;j<c;j++)
mem[y1][j]=dist[r-1][j];
}
int slow(int x1,int y1,int x2,int y2)
{
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
dist[i][j]=-1;
pq=idle;
pq.push({0,{x1,y1}});
pair<int,pair<int,int> > p;
int d,x,y;
while(pq.size())
{
p=pq.top();
pq.pop();
d=-p.first;
x=p.second.first;
y=p.second.second;
//cout<<x<<" "<<y<<" -> "<<d<<endl;
if(dist[x][y]!=-1)continue;
dist[x][y]=d;
if(x==x2&&y==y2)return d;
if(x!=r-1)pq.push({-(d+v[x][y]),{x+1,y}});
if(y)pq.push({-(d+h[x][y-1]),{x,y-1}});
if(y!=c-1)pq.push({-(d+h[x][y]),{x,y+1}});
}
assert(0==1);
}
int escape(int V1,int V2)
{
if(in<=100)
{
in++;
return slow(0,V1,r-1,V2);
}
if(run)
{
for(int j=0;j<c;j++)
dij(0,j);
run=0;
}
return mem[V1][V2];
}
/*
int H[5000][200]={
{0,2,5},
{7,1,1},
{0,4,0}
};
int V[5000][200]={
{0,0,0,2},
{0,3,4,7},
};
int main()
{
init(3,4,H,V);
cout<<escape(2,1)<<endl;//2
cout<<escape(3,3)<<endl;//7
changeV(0,0,5);
changeH(1,1,6);
cout<<escape(2,1)<<endl;//5
return 0;
}
*/
