#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
long long n,m,h[5005][205],v[5005][205],dis[5005][205][205],xx[]= {-1,0,0},yy[]= {0,-1,1},on;
void dij()
{
priority_queue<pair<long long,pair<int,int> > >q;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
for(int z=0; z<m; z++)dis[j][z][i]=1e18;
}
dis[n-1][i][i]=0;
q.push({0,{n-1,i}});
while(q.size())
{
pair<long long,pair<int,int> >z=q.top();
q.pop();
int x=z.second.first,y=z.second.second;
for(int j=0; j<3; j++)
{
int tx=x+xx[j],ty=y+yy[j],w;
if(0>tx||tx>=n||0>ty||ty>=m)continue;
if(j==0)w=v[tx][ty];
if(j==1)w=h[tx][ty];
if(j==2)w=h[x][y];
if(dis[tx][ty][i]>dis[x][y][i]+w)
{
dis[tx][ty][i]=dis[x][y][i]+w;
q.push({dis[tx][ty][i],{tx,ty}});
}
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
n=R,m=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];
}
dij();
}
void changeH(int P, int Q, int W)
{
on=1;
h[P][Q]=W;
}
void changeV(int P, int Q, int W)
{
on=1;
v[P][Q]=W;
}
int escape(int V1, int V2)
{
if(on)dij();
on=0;
return dis[0][V1][V2];
}
