#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];
bool have[maxm];
int cd(int a , int b)
{
return a * m + b;
}
void dij(int src)
{
if(have[src])
return;
have[src] = 1;
memset(d[src] , 63 , sizeof d[src]);
d[src][src] = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j + 1 < m; j++)
{
int v = cd(i , j) , u = cd(i , j + 1);
d[src][u] = min(d[src][u] , d[src][v] + w[idH[i][j]]);
d[src][v] = min(d[src][v] , d[src][u] + w[idH[i][j]]);
}
for(int j = m - 2; j >= 0; j--)
{
int v = cd(i , j) , u = cd(i , j + 1);
d[src][u] = min(d[src][u] , d[src][v] + w[idH[i][j]]);
d[src][v] = min(d[src][v] , d[src][u] + w[idH[i][j]]);
}
if(i + 1 < n)
for(int j = 0; j < m; j++)
d[src][cd(i + 1 , j)] = d[src][cd(i , j)] + w[idV[i][j]];
}
}
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;
memset(have , 0 , sizeof have);
}
void changeV(int P, int Q, int W)
{
int e = idV[P][Q];
w[e] = W;
memset(have , 0 , sizeof have);
}
int escape(int V1, int V2)
{
dij(V1);
return d[V1][cd(n - 1 , V2)];
}
