#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
int R, C;
vector<vector<int>> d, l, r;
vector<vector<int>> res;
void calc(){
for (int i=0; i<C; i++){
vector<vector<bool>> seen(R, vector<bool>(C, false));
priority_queue<pair<int,pair<int,int>>> pq;
pq.push({0, {0, i}});
while (!pq.empty()){
int dist = -pq.top().first, x = pq.top().second.first, y = pq.top().second.second;
pq.pop();
if (seen[x][y]) continue;
seen[x][y] = true;
if (x == R-1) res[i][y] = dist;
else pq.push({-(dist+d[x][y]), {x+1, y}});
if (y > 0) pq.push({-(dist+l[x][y]), {x, y-1}});
if (y < C-1) pq.push({-(dist+r[x][y]), {x, y+1}});
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
::R = R; ::C = C;
d.resize(R, vector<int>(C));
l.resize(R, vector<int>(C));
r.resize(R, vector<int>(C));
for (int i=0; i<R; i++){
for (int j=0; j<C; j++){
if (i < R-1) d[i][j] = V[i][j];
if (j > 0) l[i][j] = H[i][j-1];
if (j < C-1) r[i][j] = H[i][j];
}
}
res.resize(C, vector<int>(C));
calc();
}
void changeH(int P, int Q, int W) {
r[P][Q] = W;
l[P][Q+1] = W;
calc();
}
void changeV(int P, int Q, int W) {
d[P][Q] = W;
calc();
}
int escape(int V1, int V2) {
return res[V1][V2];
}
