#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
const int MOD = 1e9+7;
const int INF = 1e18;
#include "wombats.h"
int h[5000][200];
int v[5000][200];
int n,m;
vector<vector<vector<int>>> dp;
void calc(int las){
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
pq.push({0,{n-1,las}});
while (pq.size()){
int x = pq.top().second.first;
int y = pq.top().second.second;
int w = pq.top().first;
pq.pop();
if (dp[las][x][y]!=-1) continue;
dp[las][x][y]=w;
if (x>0 && dp[las][x-1][y]==-1){
pq.push({w+v[x-1][y],{x-1,y}});
}
if (y>0 && dp[las][x][y-1]==-1){
pq.push({w+h[x][y-1],{x,y-1}});
}
if (y<m-1 && dp[las][x][y+1]==-1){
pq.push({w+h[x][y],{x,y+1}});
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
for (int i = 0; i < R; i++){
for (int j = 0; j < C; j++){
h[i][j]=H[i][j];
v[i][j]=V[i][j];
}
}
n=R,m=C;
dp.resize(m,vector<vector<int>>(n,vector<int>(m,-1)));
}
void changeH(int P, int Q, int W){
h[P][Q]=W;
dp.clear();
dp.resize(m,vector<vector<int>>(n,vector<int>(m,-1)));
}
void changeV(int P, int Q, int W) {
v[P][Q]=W;
dp.clear();
dp.resize(m,vector<vector<int>>(n,vector<int>(m,-1)));
}
int escape(int V1, int V2) {
if (dp[V2][0][V1]==-1) calc(V2);
return dp[V2][0][V1];
}
