#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl
struct x{
lli f;
lli c;
lli val;
bool operator < (const x &a)
const {
return val > a.val;
}
};
x act;
lli hijos[5002][202][3],visitados[5002][202];
lli fil,col;
priority_queue<x> cola;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
fil = R;
col = C;
rep(i,0,R-1) {
rep(j,0,C-2) {
hijos[i][j][2] = H[i][j];
hijos[i][j+1][0] = H[i][j];
}
}
rep(i,0,R-2) {
rep(j,0,C-1) hijos[i][j][1] = V[i][j];
}
}
void changeH(int P, int Q, int W) {
hijos[P][Q][2] = W;
hijos[P][Q+1][0] = W;
}
void changeV(int P, int Q, int W) {
hijos[P][Q][1] = W;
}
int escape(int V1, int V2) {
rep(i,0,fil-1) rep(j,0,col-1) visitados[i][j] = 0;
while (!cola.empty()) cola.pop();
cola.push({0,V1,0});
while (!cola.empty()) {
act = cola.top();
cola.pop();
if (visitados[act.f][act.c] == 0) visitados[act.f][act.c] = 1;
else continue;
if (act.f == fil-1 && act.c == V2) return act.val;
if (act.c > 0 && visitados[act.f][act.c-1] == 0) cola.push({act.f,(act.c-1),(act.val + hijos[act.f][act.c][0])});
if (act.c < (col-1) && visitados[act.f][act.c+1] == 0) cola.push({act.f,(act.c+1),(act.val + hijos[act.f][act.c][2])});
if (act.f < (fil-1) && visitados[act.f+1][act.c] == 0) cola.push({(act.f+1),act.c,(act.val + hijos[act.f][act.c][1])});
}
}
