#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
const int NMAX = 1e5+10;
int H[5000][200], V[5000][200];
int R, C;
int precomp[2][2];
int pre2[20][20];
vvi dist;
int sum = 0;
bool changed;
vii adj(int r, int c){
vii n;
if(r < R-1) n.pb(mp(r+1 + R*c, V[r][c]));
if(c > 0) n.pb( mp(r+R*(c-1), H[r][c-1]) );
if(c < C-1) n.pb( mp( r+R*(c+1), H[r][c]) );
return n;
}
void dijkstra(int r, int c){
dist.assign(R, vi(C, 2e9));
priority_queue<ii, vii, greater<ii>> q;
q.push({0, r + R * c});
//cerr<<r<<" "<<c<<endl;
dist[r][c] = 0;
while(!q.empty()){
ii p = q.top(); q.pop();
int d = p.fst, u = p.snd;
int r = u%R, c = u/R;
if(dist[r][c] < d) continue;
for(ii p: adj(r, c)) {
int v = p.fst, l = p.snd;
//cout << l << endl;
int &D = dist[v%R][v/R];
if(d + l < D) {
D = d + l;
q.push({D, v});
}
}
}
}
void recomp(){
if(C == 2){
dijkstra(0, 0);
precomp[0][0] = dist[R-1][0];
precomp[0][1] = dist[R-1][1];
dijkstra(0, 1);
precomp[1][0] = dist[R-1][0];
precomp[1][1] = dist[R-1][1];
}
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
FOR(i, 0, r) FOR(j, 0, c) {H[i][j] = h[i][j]; V[i][j] = v[i][j]; sum += V[i][j];}
R = r;
C = c;
dist.assign(R, vi(C, 2e9));
recomp();
changed = 0;
if(R <= 20 and C <= 20){
FOR(i, 0, C){
dijkstra(0, i);
FOR(j, 0, C) pre2[i][j] = dist[R-1][j];
}
}
}
void changeH(int P, int Q, int W) {
changed = 1;
H[P][Q] = W;
recomp();
}
void changeV(int P, int Q, int W) {
sum -= V[P][Q];
V[P][Q] = W;
sum += W;
changed = 1;
recomp();
}
int escape(int V1, int V2) {
if(C == 1) return sum;
if(C == 2) {
return precomp[V1][V2];
}
if(!changed and R <= 20 and C <= 20) {
return pre2[V1][V2];
}
dijkstra(0, V1);
/*FOR(i, 0, R) {
FOR(j, 0, C) cout << dist[i][j] << " ";
cout << endl;
}*/
return dist[R-1][V2];
}
