#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
using pii = pair<long long, long long>;
const long long INF = 1e12;
int n, m;
vector<vector<long long>> h(5001, vector<long long> (201)), v = h, dp = h, memo;
bool sol = false;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R, m = C;
for(int i = 0 ; i < R ; i++)
{
for(int j = 0 ; j < C - 1 ; j++)
{
h[i][j] = H[i][j];
}
}
for(int i = 0 ; i < R - 1 ; i++)
{
for(int j = 0 ; j < C ; j++)
{
v[i][j] = V[i][j];
}
}
memo = vector<vector<long long>> (m, vector<long long> (m, -1));
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
sol = false;
memo = vector<vector<long long>> (m, vector<long long> (m, -1));
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
sol = false;
memo = vector<vector<long long>> (m, vector<long long> (m, -1));
}
int escape(int V1, int V2)
{
if(memo[V1][V2] == -1)
{
for(int i = 0 ; i < m ; i++)
{
dp[n-1][i] = INF;
}
dp[n-1][V2] = 0;
for(int i = n - 1 ; i >= 0 ; i--)
{
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int j = 0 ; j < m ; j++)
{
q.push({dp[i][j], j});
}
while(q.size())
{
long long j, dist;
tie(dist, j) = q.top();
q.pop();
//if(dp[i][j] < dist)
// continue;
if(j - 1 >= 0 and dp[i][j-1] > dist + h[i][j-1])
{
dp[i][j-1] = dist + h[i][j-1];
q.push({dp[i][j-1], j-1});
}
if(j + 1 < m and dp[i][j+1] > dist + h[i][j])
{
dp[i][j+1] = dist + h[i][j];
q.push({dp[i][j+1], j+1});
}
}
for(int j = 0 ; j < m and i != 0; j++)
{
dp[i-1][j] = dp[i][j] + v[i-1][j];
}
}
for(int i = 0 ; i < m ; i++)
{
memo[i][V2] = dp[0][i];
}
}
return memo[V1][V2];
}
