#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y,d;
};
vector<vector<vector<node>>>adj;
int dist3[200][200];
int n,m;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
/* ... */
n = R,m = C;
adj.resize(R,vector<vector<node>>(C));
for (int i = 0;i<R;++i){
for (int j = 0;j<C - 1;++j){
adj[i][j].push_back({i,j + 1,H[i][j]});
adj[i][j + 1].push_back({i,j,H[i][j]});
}
}
for (int i = 0;i<R - 1;++i){
for (int j = 0;j<C;++j){
adj[i][j].push_back({i + 1,j,V[i][j]});
adj[i + 1][j].push_back({i,j,V[i][j]});
}
}
for (int i = 0;i<m;++i){
vector<vector<int>>dist1(n,vector<int>(m,1e9));
priority_queue<pair<int,pair<int,int>>>q;
q.push({0,{0,i}});
dist1[0][i] = 0;
while(!q.empty()){
auto u = q.top();
q.pop();
if (dist1[u.second.first][u.second.second] != -u.first)continue;
for (auto x:adj[u.second.first][u.second.second]){
if (u.second.first - x.x > 0)continue;
if (dist1[x.x][x.y] > -u.first + x.d){
dist1[x.x][x.y] = -u.first + x.d;
q.push({-dist1[x.x][x.y],{x.x,x.y}});
}
}
}
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[n - 1][j];
}
}
}
void changeH(int P, int Q, int W) {
for (auto &x:adj[P][Q]){
if (x.y == Q + 1){
x.d = W;
}
}
for (auto &x:adj[P][Q + 1]){
if (x.y == Q){
x.d = W;
}
}
for (int i = 0;i<m;++i){
vector<vector<int>>dist1(n,vector<int>(m,1e9));
priority_queue<pair<int,pair<int,int>>>q;
q.push({0,{0,i}});
dist1[0][i] = 0;
while(!q.empty()){
auto u = q.top();
q.pop();
if (dist1[u.second.first][u.second.second] != -u.first)continue;
for (auto x:adj[u.second.first][u.second.second]){
if (u.second.first - x.x > 0)continue;
if (dist1[x.x][x.y] > -u.first + x.d){
dist1[x.x][x.y] = -u.first + x.d;
q.push({-dist1[x.x][x.y],{x.x,x.y}});
}
}
}
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[n - 1][j];
}
}
}
void changeV(int P, int Q, int W) {
for (auto &x:adj[P][Q]){
if (x.x == P + 1){
x.d = W;
}
}
for (auto &x:adj[P + 1][Q]){
if (x.x == P){
x.d = W;
}
}
for (int i = 0;i<m;++i){
vector<vector<int>>dist1(n,vector<int>(m,1e9));
priority_queue<pair<int,pair<int,int>>>q;
q.push({0,{0,i}});
dist1[0][i] = 0;
while(!q.empty()){
auto u = q.top();
q.pop();
if (dist1[u.second.first][u.second.second] != -u.first)continue;
for (auto x:adj[u.second.first][u.second.second]){
if (u.second.first - x.x > 0)continue;
if (dist1[x.x][x.y] > -u.first + x.d){
dist1[x.x][x.y] = -u.first + x.d;
q.push({-dist1[x.x][x.y],{x.x,x.y}});
}
}
}
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[n - 1][j];
}
}
}
int escape(int V1, int V2) {
return dist3[V1][V2];
}
