#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define mid (l + r) / 2
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005
#define M 201
const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
static int H[5000][200];
static int V[5000][200];
int h[5000][200], v[5000][200], r, c;
int ans[200][5000][200];
void dijkstra(){
for (int I = 0; I < c; I++){
priority_queue<pii, vector<pii>, less<pii>> q;
for(int i = 0; i < r; i++) for (int j = 0; j < c; j++) ans[I][i][j] = modulo;
ans[I][r - 1][I] = 0;
q.push({0, (r - 1) * M + I});
while(!q.empty()){
pii tmp = q.top();
q.pop();
int d = -tmp.st, x = tmp.nd / M, y = tmp.nd % M;
if (d > ans[I][x][y]) continue;
if (y + 1 < c){
if (ans[I][x][y + 1] > d + h[x][y]){
ans[I][x][y + 1] = d + h[x][y];
q.push({-ans[I][x][y + 1], x * M + y + 1});
}
}
if (y > 0){
if (ans[I][x][y - 1] > d + h[x][y - 1]){
ans[I][x][y - 1] = d + h[x][y - 1];
q.push({-ans[I][x][y - 1], x * M + y - 1});
}
}
if (x > 0){
if (ans[I][x - 1][y] > d + v[x - 1][y]){
ans[I][x - 1][y] = d + v[x - 1][y];
q.push({-ans[I][x - 1][y], (x - 1) * M + y});
}
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R, c = C;
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];
//cout<<h[i][j]<<sp<<v[i][j]<<sp;
}
//cout<<endl;
}
dijkstra();
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
dijkstra();
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
dijkstra();
}
int escape(int V1, int V2) {
return ans[V2][0][V1];
}
