#include "wombats.h"
#include <bits/stdc++.h>
using std::array;
constexpr int INF = (1 << 30) - 1;
const int MAX_R = 5000;
const int MAX_C = 200;
const int BLOCK = 10;
const int SEG = 512;
template <class T>
bool setmin(T& x, const T& y) {
if (x > y) {
x = y;
return true;
}
return false;
}
// grid data
int R, C;
int H[MAX_R][MAX_C];
int V[MAX_R][MAX_C];
// segtree data
array<array<int, MAX_C>, MAX_C> dist[2 * SEG];
int append[2 * SEG];
void calc_group(const int g) {
const int i0 = BLOCK * g;
const int i1 = std::min(R, i0 + BLOCK);
static array<int, MAX_C> accum = {};
static array<int, MAX_C> next = {};
const auto setup = [&](const int i) {
for (int j = 0; j < C - 1; ++j)
accum[j + 1] = accum[j] + H[i][j];
};
setup(i0);
auto& dp = dist[SEG + g];
for (int a = 0; a < C; ++a)
for (int b = a; b < C; ++b)
dp[a][b] = dp[b][a] = accum[b] - accum[a];
for (int i = i0; i < i1 - 1; ++i) {
setup(i + 1);
for (int a = 0; a < C; ++a) {
next.fill(INF);
for (int b = 0, min = INF; b < C; ++b) {
setmin(min, dp[a][b] + V[i][b] - accum[b]);
setmin(next[b], min + accum[b]);
}
for (int b = C - 1, min = INF; b >= 0; --b) {
setmin(min, dp[a][b] + V[i][b] + accum[b]);
setmin(next[b], min - accum[b]);
}
dp[a] = next;
}
}
}
void fetch(const int g) {
const int l = 2 * g;
const int r = 2 * g + 1;
append[g] = append[r];
if (append[l] == R - 1) {
dist[g] = dist[l];
return;
}
auto& dp = dist[g];
for (int a = 0; a < C; ++a)
for (int b = 0; b < C; ++b)
dp[a][b] = INF;
static array<array<int, MAX_C>, MAX_C> best = {};
const auto check = [&](const int a, const int c, const int b) {
if (setmin(dp[a][b], dist[l][a][c] + V[append[l]][c] + dist[r][c][b]))
best[a][b] = c;
};
for (int a = 0; a < C; ++a)
for (int b = 0; b < C; ++b)
check(a, b, a);
for (int len = 1; len < C; ++len) {
for (int a = 0; a + len < C; ++a)
for (int b = best[a][a + len - 1]; b <= best[a + 1][a + len]; ++b)
check(a, b, a + len);
for (int a = len; a < C; ++a)
for (int b = best[a - 1][a - len]; b <= best[a][a - len + 1]; ++b)
check(a, b, a - len);
}
}
void init(int r, int c, int h[MAX_R][MAX_C], int v[MAX_R][MAX_C]) {
R = r, C = c;
std::memcpy(H, h, sizeof(H));
std::memcpy(V, v, sizeof(V));
const int n = (R + BLOCK - 1) / BLOCK;
for (int g = 0; g < n; ++g)
calc_group(g);
for (int g = 0; g < SEG; ++g)
append[SEG + g] = std::min(BLOCK * (g + 1) - 1, R - 1);
for (int g = SEG - 1; g > 0; --g)
fetch(g);
}
void changeH(int p, int q, int w) {
H[p][q] = w;
const int g = p / BLOCK;
calc_group(g);
for (int k = SEG + g; (k >>= 1) > 0;)
fetch(k);
}
void changeV(int p, int q, int w) {
V[p][q] = w;
const int g = p / BLOCK;
calc_group(g);
for (int k = SEG + g; (k >>= 1) > 0;)
fetch(k);
}
int escape(int v0, int v1) {
return dist[1][v0][v1];
}
