#include "wombats.h"
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace std;
typedef int ll;
typedef pair<ll,ll>pairll;
#define pb push_back
#define fr first
#define sc second
#define A 16
#define INF 1000000007
ll h[5007][207],v[5007][207],n,m,f[207],res[207][207],g[5007][207],l[2][207];
ll d[5007/A+1][207][207];
priority_queue<pairll, vector<pairll>, greater<pairll> >q;
void S(ll x){
//cout<<x<<endl;
ll y=x;
y*=A;
for(int k=0;k<m;k++){
for(int i=y;i<=y+A;i++){
for(int j=0;j<m;j++){
g[i][j]=INF;
}
}
g[y][k]=0;
q.push({0,y*m+k});
while(q.size()>0){
ll m1=q.top().fr;
ll x1=q.top().sc/m;
ll y1=q.top().sc%m;
q.pop();
if(x1<min(n-1,y+A)){
if(g[x1+1][y1]>m1+v[x1][y1]){
g[x1+1][y1]=m1+v[x1][y1];
q.push({m1+v[x1][y1],m*(x1+1)+y1});
}
}
if(y1>0){
if(g[x1][y1-1]>m1+h[x1][y1-1]){
g[x1][y1-1]=m1+h[x1][y1-1];
q.push({m1+h[x1][y1-1],x1*m+y1-1});
}
}
if(y1<m-1){
if(g[x1][y1+1]>m1+h[x1][y1]){
g[x1][y1+1]=m1+h[x1][y1];
q.push({m1+h[x1][y1],x1*m+y1+1});
}
}
}
for(int j=0;j<m;j++){
d[x][k][j]=g[min(n-1,y+A)][j];
}
}
return ;
}
void R(ll x){
f[x]=1;
for(int i=0;i<m;i++){
l[0][i]=INF;
}
l[0][x]=0;
for(int i=0;i<=(n-1)/A;i++){
for(int j=0;j<m;j++){
l[1][j]=INF;
for(int k=0;k<m;k++){
l[1][j]=min(l[1][j],l[0][k]+d[i][k][j]);
}
}
swap(l[0],l[1]);
}
for(int i=0;i<m;i++){
res[x][i]=l[0][i];
}
return ;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n=R;
m=C;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
h[i][j]=H[i][j];
v[i][j]=V[i][j];
}
}
for(int i=0;i<=(n-1)/A;i++){
S(i);
}
return ;
}
void changeH(int x, int y, int val) {
h[x][y]=val;
for(int i=0;i<m;i++){
f[i]=0;
}
if(x%A==0){
if(x!=0)S(x/A-1);
}
S(x/A);
return ;
}
void changeV(int x, int y, int val) {
for(int i=0;i<m;i++){
f[i]=0;
}
v[x][y]=val;
S(x/A);
return ;
}
int escape(int y1, int y2) {
if(f[y1]==0){
R(y1);
}
return res[y1][y2];
}
