#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (1 << 30) - 1;
const ll LINF = (1LL << 60) - 1LL;
int type, h, w, sum1;
struct edge {
int y, x, cst;
};
vector<edge> G[110][110];
int d[110][110], dp0[5001][2], dp1[5001][2];
int v[5000][200], hh[5000][200];
void recalc() {
for (int i = 0; i <= h; i++) {
dp0[i][0] = INF;
dp0[i][1] = INF;
dp1[i][0] = INF;
dp1[i][1] = INF;
}
dp0[0][0] = 0;
dp0[0][1] = hh[0][0];
dp1[0][1] = 0;
dp1[0][0] = hh[0][0];
for (int i = 1; i < h; i++) {
dp0[i][0] = min(dp0[i - 1][0] + v[i - 1][0],
dp0[i - 1][1] + v[i - 1][1] + hh[i][0]);
dp0[i][1] = min(dp0[i - 1][1] + v[i - 1][1],
dp0[i - 1][0] + v[i - 1][0] + hh[i][0]);
dp1[i][0] = min(dp1[i - 1][0] + v[i - 1][0],
dp1[i - 1][1] + v[i - 1][1] + hh[i][0]);
dp1[i][1] = min(dp1[i - 1][1] + v[i - 1][1],
dp1[i - 1][0] + v[i - 1][0] + hh[i][0]);
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
h = R, w = C;
sum1 = 0;
for (int i = 0; i < h - 1; i++) {
for (int j = 0; j < w; j++) {
v[i][j] = V[i][j];
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w - 1; j++) {
hh[i][j] = H[i][j];
}
}
if (w == 1) {
type = 1;
for (int i = 0; i < h - 1; i++) {
sum1 += V[i][0];
}
} else if (h <= 20 && w <= 20) {
type = 2;
} else if (h <= 100 && w <= 100) {
type = 3;
} else if (w == 2) {
type = 4;
}
if (type == 2 || type == 3) {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w - 1; j++) {
G[i][j].push_back(edge{i, j + 1, H[i][j]});
G[i][j + 1].push_back(edge{i, j, H[i][j]});
}
}
for (int i = 0; i < h - 1; i++) {
for (int j = 0; j < w; j++) {
G[i][j].push_back(edge{i + 1, j, V[i][j]});
}
}
} else if (type == 4) {
recalc();
}
}
void changeH(int P, int Q, int W) {
if (type == 2 || type == 3) {
vector<edge> to;
for (auto &e : G[P][Q]) {
if (e.y == P && e.x == Q + 1) {
continue;
}
to.push_back(e);
}
to.push_back(edge{P, Q + 1, W});
G[P][Q] = to;
to.clear();
for (auto &e : G[P][Q + 1]) {
if (e.y == P && e.x == Q) {
continue;
}
to.push_back(e);
}
to.push_back(edge{P, Q, W});
G[P][Q + 1] = to;
} else if (type == 4) {
hh[P][Q] = W;
recalc();
}
}
void changeV(int P, int Q, int W) {
if (type == 1) {
sum1 -= v[P][Q];
sum1 += W;
v[P][Q] = W;
} else if (type == 2 || type == 3) {
vector<edge> to;
for (auto &e : G[P][Q]) {
if (e.y == P + 1 && e.x == Q) {
continue;
}
to.push_back(e);
}
to.push_back(edge{P + 1, Q, W});
G[P][Q] = to;
} else if (type == 4) {
v[P][Q] = W;
recalc();
}
}
int escape(int V1, int V2) {
if (type == 1) {
return sum1;
} else if (type == 2 || type == 3) {
priority_queue<pair<int, P>, vector<pair<int, P>>,
greater<pair<int, P>>>
q;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
d[i][j] = INF;
}
}
d[0][V1] = 0;
q.push(make_pair(0, P(0, V1)));
while (!q.empty()) {
int ds = q.top().first, y = q.top().second.first,
x = q.top().second.second;
q.pop();
if (ds > d[y][x]) {
continue;
}
for (auto &e : G[y][x]) {
if (d[e.y][e.x] > d[y][x] + e.cst) {
d[e.y][e.x] = d[y][x] + e.cst;
q.push(make_pair(d[e.y][e.x], P(e.y, e.x)));
}
}
}
return d[h - 1][V2];
} else if (type == 4) {
if (V1 == 0) {
return dp0[h - 1][V2];
} else {
return dp1[h - 1][V2];
}
}
}
