#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.begin();
#define all(x) x.begin(),x.end();
const int inf = 1e9 + 7;
int r,c,h[5000][200],v[5000][200];
int ans[200][200];
vector<vector<int>> dijkstra_up(int x , int y){
vector vis(r , vector < int > (c , inf));
priority_queue<array<int,3>> pq;
pq.push({0,x,y});
while(!pq.empty()){
auto tmp = pq.top();
pq.pop();
if(vis[tmp[1]][tmp[2]] != inf)continue;
vis[tmp[1]][tmp[2]] = -tmp[0];
if(tmp[2] > 0)pq.push({tmp[0] - h[tmp[1]][tmp[2]-1],tmp[1],tmp[2]-1});
if(tmp[2] < c-1)pq.push({tmp[0] - h[tmp[1]][tmp[2]],tmp[1],tmp[2]+1});
if(tmp[1] > 0)pq.push({tmp[0] - v[tmp[1]-1][tmp[2]],tmp[1]-1,tmp[2]});
}
return vis;
}
vector<vector<int>> dijkstra_down(int x , int y){
// cout << "dijkstra_down : " << x << " " << y << endl;
vector vis(r , vector < int > (c , inf));
priority_queue<array<int,3>> pq;
pq.push({0,x,y});
// cout << "starting" << endl;
while(!pq.empty()){
auto tmp = pq.top();
pq.pop();
// cout << "ok ? " << tmp[0] << " " << tmp[1] << " " << tmp[2] << endl;
if(vis[tmp[1]][tmp[2]] != inf)continue;
vis[tmp[1]][tmp[2]] = -tmp[0];
if(tmp[2] > 0)pq.push({tmp[0] - h[tmp[1]][tmp[2]-1],tmp[1],tmp[2]-1});
if(tmp[2] < c-1)pq.push({tmp[0] - h[tmp[1]][tmp[2]],tmp[1],tmp[2]+1});
if(tmp[1] < r-1)pq.push({tmp[0] - v[tmp[1]][tmp[2]],tmp[1]+1,tmp[2]});
}
// cout << "done" << endl;
return vis;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
// cout << "flag0" << endl;
for(int i = 0;i<200;i++){
for(int j = 0;j<200;j++){
ans[i][j] = inf;
}
}
r = R , c = C;
// cout << "flag1" << endl;
for(int i = 0;i<5000;i++){
for(int j = 0;j<200;j++){
h[i][j] = H[i][j];
v[i][j] = V[i][j];
}
}
// cout << "flag2" << endl;
for(int i = 0;i<C;i++){
auto dist = dijkstra_down(0,i);
for(int j = 0;j<C;j++){
ans[i][j] = min(ans[i][j] , dist[R-1][j]);
}
}
// cout << "flag3" << endl;
}
void changeH(int P, int Q, int W) {
for(int i = 0;i<200;i++){
for(int j = 0;j<200;j++){
ans[i][j] = inf;
}
}
h[P][Q] = W;
for(int i = 0;i<c;i++){
auto dist = dijkstra_down(0,i);
for(int j = 0;j<c;j++){
ans[i][j] = min(ans[i][j] , dist[r-1][j]);
}
}
// // sol yukari , sag asagi
// auto distup = dijkstra_up(P,Q);
// auto distdown = dijkstra_down(P,Q+1);
// for(int i = 0;i<c;i++){
// for(int j = 0;j<c;j++){
// ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
// }
// }
// // sol asagi , sag yukari
// distup = dijkstra_up(P,Q+1);
// distdown = dijkstra_down(P,Q);
// for(int i = 0;i<c;i++){
// for(int j = 0;j<c;j++){
// ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
// }
// }
}
void changeV(int P, int Q, int W) {
for(int i = 0;i<200;i++){
for(int j = 0;j<200;j++){
ans[i][j] = inf;
}
}
v[P][Q] = W;
for(int i = 0;i<c;i++){
auto dist = dijkstra_down(0,i);
for(int j = 0;j<c;j++){
ans[i][j] = min(ans[i][j] , dist[r-1][j]);
}
}
// // yukari yukari , asagi asagi
// auto distup = dijkstra_up(P,Q);
// auto distdown = dijkstra_down(P+1,Q);
// for(int i = 0;i<c;i++){
// for(int j = 0;j<c;j++){
// ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
// }
// }
// // yukari asagi , asagi yukari
// distup = dijkstra_up(P+1,Q);
// distdown = dijkstra_down(P,Q);
// for(int i = 0;i<c;i++){
// for(int j = 0;j<c;j++){
// ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
// }
// }
}
int escape(int V1, int V2) {
return ans[V1][V2];
}
