#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
int tr[5000][200][3];
int delta[3][2] = {{0, 1}, {0, -1}, {1, 0}};
int dist[5000][200];
int r, c;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r= R;
c= C;
for(int p = 0; p<R; p++){
for(int q= 0; q<C-1; q++){
tr[p][q][0] = H[p][q];
tr[p][q+1][1] = H[p][q];
}
for(int q= 0; q<C; q++){
tr[p][q][2] = V[p][q];
}
}
}
void changeH(int P, int Q, int W) {
tr[P][Q][0] = W;
tr[P][Q+1][1] = W;
}
void changeV(int P, int Q, int W) {
tr[P][Q][2] = W;
}
vector<pair<pii, int>> gen_adj(pii pos){
vector<pair<pii, int>> res;
for(int trid = 0; trid<3; trid++){
pii potential = {pos.first + delta[trid][0], pos.second + delta[trid][1]};
if(potential.first<r && potential.second>=0 && potential.second<c){
res.push_back({potential, tr[pos.first][pos.second][trid]});
}
}
return res;
}
int dijkstra(pii begin, pii dest){
for(int i = 0; i<r; i++){
for(int j = 0; j<c; j++){
dist[i][j] = 1e9;
}
}
priority_queue<pair<int, pii>> pq;
pq.push({0, begin});
dist[begin.first][begin.second] = 0;
while(pq.size()>0){
auto cur = pq.top();
pq.pop();
pii pos= cur.second;
int d = -cur.first;
//cout<<pos.first<<" "<<pos.second<<" "<<d<<endl;
if(d== dist[pos.first][pos.second]){
auto adj = gen_adj(pos);
for(auto e: adj){
if(d + e.second< dist[e.first.first][e.first.second]){
dist[e.first.first][e.first.second]= d + e.second;
pq.push({-d-e.second, e.first});
}
}
}
}
return dist[dest.first][dest.second];
}
int escape(int V1, int V2) {
return dijkstra(pii(0, V1), pii(r-1, V2));
}
