#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pr pair<int, int>
#define tri array<int, 3>
const int INF = 1e9 + 7;
vector<vector<vector<int>>> edge;
vector<vector<vector<int>>> d;
int r, c;
int x[3] = {0, 1, 0}, y[3] = {-1, 0, 1};
void comp(int v) {
priority_queue<tri, vector<tri>, greater<tri>> q;
q.push({0, 0, v});
d[v][0][v] = 0;
while (!q.empty()) {
auto [dist, i, j] = q.top(); q.pop();
if (d[v][i][j] < dist) continue;
for (int t = 0; t < 3; t++) {
if (ok(i, j, t)) {
int te = dist + edge[i][j][t];
if (d[v][i + x[t]][j + y[t]] > te) {
q.push({te, i + x[t], j + y[t]});
d[v][i + x[t]][j + y[t]] = te;
}
}
}
}
}
bool ok(int i, int j, int t) {
i += x[t]; j += y[t];
if (i < 0 || j < 0 || i >= r || j >= c) return 0;
else return 1;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R; c = C;
edge.resize(R, vector<vector<int>>(C, vector<int>(3, INF)));
d.assign(c, vector<vector<int>> (r, vector<int>(c, INF)));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (j > 0)
edge[i][j][0] = H[i][j-1];
if (i + 1 < r)
edge[i][j][1] = V[i][j];
if (j < c-1)
edge[i][j][2] = H[i][j];
}
}
d.assign(c, vector<vector<int>> (r, vector<int>(c, INF)));
for (int i = 0; i < c; i++) comp(i);
}
void changeH(int P, int Q, int W) {
edge[P][Q][2] = W;
if (Q + 1 < c)
edge[P][Q+1][0] = W;
d.assign(c, vector<vector<int>> (r, vector<int>(c, INF)));
for (int i = 0; i < c; i++) comp(i);
}
void changeV(int P, int Q, int W) {
edge[P][Q][1] = W;
d.assign(c, vector<vector<int>> (r, vector<int>(c, INF)));
for (int i = 0; i < c; i++) comp(i);
}
int escape(int V1, int V2) {
return d[V1][r-1][V2];
}
