#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 3e2;
int HOR[5000][200], VER[5000][200];
int get_weight(int x, int y, char c){
// if (c == 'U') return VER[x - 1][y];
if (c == 'D') return VER[x][y];
if (c == 'L') return HOR[x][y - 1];
if (c == 'R') return HOR[x][y];
assert(false);
return -1;
}
vector<int> dv;
string dc = "RDL";
int N, M;
int get_weight(int x, char c){
return get_weight(x / M, x % M, c);
}
#define MP make_pair
int answer_sub1 = 0;
void init(int R, int C, int _H[5000][200], int _V[5000][200]) {
N = R, M = C;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
if (j < M - 1) HOR[i][j] = _H[i][j];
if (i < N - 1) VER[i][j] = _V[i][j];
}
if (i < N - 1) answer_sub1 += VER[i][0];
}
dv = {1, M, -1};
}
void changeH(int P, int Q, int W) {
HOR[P][Q] = W;
}
void changeV(int P, int Q, int W) {
answer_sub1 += W - VER[P][Q];
VER[P][Q] = W;
}
int escape(int V1, int V2) {
if (M == 1) return answer_sub1;
priority_queue<pair<int, int>> pq;
pq.push(MP(0, V1));
vector<int> d(N * M, 2e9 + 5);
vector<bool> processed(N * M, false);
d[V1] = 0;
while (!pq.empty()){
int x = pq.top().second; pq.pop();
if (processed[x]) continue;
processed[x] = true;
for (int i = 0; i < 3; i++){
int y = x + dv[i];
if (y >= N * M || x % M == M - 1 && dc[i] == 'R' || x % M == 0 && dc[i] == 'L') continue;
int w = get_weight(x, dc[i]);
if (d[y] > d[x] + w){
d[y] = d[x] + w;
pq.push(MP(-d[y], y));
}
}
}
return d[(N - 1) * M + V2];
}
