#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxR = 5000 + 2;
const int MaxC = 200 + 2;
const int Inf = 0x3f3f3f3f;
template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }
void init(int R, int C, int H[5000][200], int V[5000][200]);
void changeH(int P, int Q, int W);
void changeV(int P, int Q, int W);
int escape(int V1, int V2);
int r, c;
int h[MaxR][MaxC];
int v[MaxR][MaxC];
int dp[MaxR][MaxC];
int tmp[MaxC];
void bfs(int u) {
for (int i = 0; i < c; ++i)
tmp[i] = Inf;
tmp[u] = 0;
for (int i = 0; i < r; ++i) {
priority_queue<pair<int, int>> q;
for (int j = 0; j < c; ++j) if (tmp[j] != Inf)
q.emplace(-tmp[j], j);
while (!q.empty()) {
auto [w, u] = q.top(); q.pop();
w = -w;
if (u + 1 < c) {
if (minimize(tmp[u + 1], tmp[u] + h[i][u]))
q.emplace(-tmp[u + 1], u + 1);
}
if (u > 0) {
if (minimize(tmp[u - 1], tmp[u] + h[i][u - 1]))
q.emplace(-tmp[u - 1], u - 1);
}
}
if (i + 1 < r)
for (int j = 0; j < c; ++j)
tmp[j] += v[i][j];
}
for (int j = 0; j < c; ++j)
dp[u][j] = tmp[j];
}
void build() {
for (int i = 0; i < c; ++i) {
bfs(i);
}
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
build();
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
build();
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R;
c = C;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c - 1; ++j)
h[i][j] = H[i][j];
for (int i = 0; i - 1 < r; ++i)
for (int j = 0; j < c; ++j)
v[i][j] = V[i][j];
build();
}
int escape(int V1, int V2) {
return dp[V1][V2];
}
