#include "wombats.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
int hor[5000][200], ver[5000][200], dist[5000][200];
int n, m;
bool isEligible(int x, int y){
return x > -1 && x < n && y > -1 && y < m;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
if(R*C > 10000) exit(0);
n = R; m = C;
for(int i = 0; i < n-1; i++)
for(int j = 0; j < m; j++)
ver[i][j] = V[i][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < m-1; j++)
hor[i][j] = H[i][j];
}
void changeH(int P, int Q, int W){
hor[P][Q] = W;
}
void changeV(int P, int Q, int W){
ver[P][Q] = W;
}
int escape(int V1, int V2) {
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
dist[i][j] = 2e9;
}
}
dist[0][V1] = 0;
priority_queue <pair <int, pii>> K;
K.push(mp(0, mp(0, V1)));
while(!K.empty()){
auto v = K.top().second; K.pop();
if(isEligible(v.first, v.second-1) && dist[v.first][v.second-1] > dist[v.first][v.second]+hor[v.first][v.second-1]){
dist[v.first][v.second-1] = dist[v.first][v.second]+hor[v.first][v.second-1];
K.push(mp(-dist[v.first][v.second-1], mp(v.first, v.second-1)));
}
if(isEligible(v.first, v.second+1) && dist[v.first][v.second+1] > dist[v.first][v.second]+hor[v.first][v.second]){
dist[v.first][v.second+1] = dist[v.first][v.second]+hor[v.first][v.second];
K.push(mp(-dist[v.first][v.second+1], mp(v.first, v.second+1)));
}
if(isEligible(v.first+1, v.second) && dist[v.first+1][v.second] > dist[v.first][v.second]+ver[v.first][v.second]){
dist[v.first+1][v.second] = dist[v.first][v.second]+ver[v.first][v.second];
K.push(mp(-dist[v.first+1][v.second], mp(v.first+1, v.second)));
}
}
return dist[n-1][V2];
}
