#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n, m;
int v[5000][200], h[5000][200];
int ans[101][101];
map<pii, int> mp;
int id;
vector<vector<pii>> adj;
void calc() {
memset(ans, -1, sizeof(ans));
for (int i=0; i<m; i++) {
int s = mp[{0, i}];
vector<int> dis(id, 1e9);
dis[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (dis[u] != d) continue;
for (auto [v, w] : adj[u]) {
if (dis[v] > dis[u]+w) {
dis[v] = dis[u]+w;
pq.push({dis[v], v});
}
}
}
for (int j=0; j<m; j++) {
ans[i][j] = dis[mp[{n-1, j}]];
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R;
m = C;
id=0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
v[i][j] = V[i][j];
h[i][j] = H[i][j];
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
mp[{i, j}] = id++;
}
}
adj.assign(id, {});
for (int i=0; i<n; i++) {
for (int j=0; j<m-1; j++) {
int a = mp[{i, j}];
int b = mp[{i, j+1}];
adj[a].push_back({b, h[i][j]});
adj[b].push_back({a, h[i][j]});
}
}
for (int i=0; i<n-1; i++) {
for (int j=0; j<m; j++) {
int a = mp[{i, j}];
int b = mp[{i+1, j}];
adj[a].push_back({b, v[i][j]});
}
}
calc();
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
adj.assign(id, {});
for (int i=0; i<n; i++) {
for (int j=0; j<m-1; j++) {
int a = mp[{i, j}];
int b = mp[{i, j+1}];
adj[a].push_back({b, h[i][j]});
adj[b].push_back({a, h[i][j]});
}
}
for (int i=0; i<n-1; i++) {
for (int j=0; j<m; j++) {
int a = mp[{i, j}];
int b = mp[{i+1, j}];
adj[a].push_back({b, v[i][j]});
}
}
//cout << "NEW CALC: ";
calc();
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
adj.assign(id, {});
for (int i=0; i<n; i++) {
for (int j=0; j<m-1; j++) {
int a = mp[{i, j}];
int b = mp[{i, j+1}];
adj[a].push_back({b, h[i][j]});
adj[b].push_back({a, h[i][j]});
}
}
for (int i=0; i<n-1; i++) {
for (int j=0; j<m; j++) {
int a = mp[{i, j}];
int b = mp[{i+1, j}];
adj[a].push_back({b, v[i][j]});
}
}
//cout << "NEWCALC: " << endl;
calc();
}
int escape(int V1, int V2) {
return ans[V1][V2];
}
