#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 5e3 + 20;
const int maxm = 1e2 + 20;
const int maxv = maxn * maxm;
const int maxe = maxn * maxm * 2;
int idH[maxn][maxm] , idV[maxn][maxm] , id;
int from[maxe] , to[maxe] , w[maxe] , n , m;
vector<int> adj[maxv];
int d[maxm][maxv];
int cd(int a , int b)
{
return a * m + b;
}
void dij(int src)
{
memset(d[src] , 63 , sizeof d[src]);
d[src][src] = 0;
set<pair<int , int> > st;
st.insert({0 , src});
while(!st.empty())
{
int v = st.begin() -> second , W = st.begin() -> first;
st.erase(st.begin());
if(d[src][v] != W)
continue;
for(auto e : adj[v])
{
int u = from[e] ^ to[e] ^ v;
if(d[src][u] > d[src][v] + w[e])
{
d[src][u] = d[src][v] + w[e];
st.insert({d[src][u] , u});
}
}
}
}
void build()
{
for(int i = 0; i < m; i++)
dij(i);
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
n = R , m = C;
for(int i = 0; i < n; i++)
for(int j = 0; j + 1 < m; j++)
{
int a = cd(i , j) , b = cd(i , j + 1);
adj[a].pb(id);
adj[b].pb(id);
from[id] = a , to[id] = b , w[id] = H[i][j];
idH[i][j] = id++;
}
for(int i = 0; i + 1 < n; i++)
for(int j = 0; j < m; j++)
{
int a = cd(i , j) , b = cd(i + 1 , j);
adj[a].pb(id);
from[id] = a , to[id] = b , w[id] = V[i][j];
idV[i][j] = id++;
}
build();
}
void changeH(int P, int Q, int W)
{
int e = idH[P][Q];
w[e] = W;
build();
}
void changeV(int P, int Q, int W)
{
int e = idV[P][Q];
w[e] = W;
build();
}
int escape(int V1, int V2)
{
return d[V1][cd(n - 1 , V2)];
}
