#include "wombats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
const int L = 15;
const int pinf = numeric_limits<int>::max() / 2;
const int ninf = numeric_limits<int>::min() / 2;
int R, C;
vector<vector<int>> H, V;
namespace DPHelper {
vector<vector<int>> base_get(int r) {
vector<vector<int>> ret(C, vector<int>(C, pinf));
for (int k = 0; k < C; k++) {
for (int i = 0; i < C - k; i++) {
if (k == 0)
ret[i][i] = 0;
else
ret[i][i + k] = ret[i + k][i] = ret[i + 1][i + k] + H[r][i];
}
}
if (r != R - 1) {
for (int i = 0; i < C; i++)
for (int j = 0; j < C; j++)
ret[i][j] += V[r][j];
}
return ret;
}
vector<vector<int>> mer(const vector<vector<int>>& lhs, const vector<vector<int>>& rhs) {
vector<vector<int>> ret(C, vector<int>(C, pinf));
vector<vector<int>> opt(C, vector<int>(C));
for (int k = 0; k < C; k++) {
for (int i = 0; i < C - k; i++) {
if (k == 0) {
for (int j = 0; j < C; j++) {
if (ret[i][i] > lhs[i][j] + rhs[j][i]) {
ret[i][i] = lhs[i][j] + rhs[j][i];
opt[i][i] = j;
}
}
} else {
for (int j = opt[i][i + k - 1]; j <= opt[i + 1][i + k]; j++) {
if (ret[i][i + k] > lhs[i][j] + rhs[j][i + k]) {
ret[i][i + k] = lhs[i][j] + rhs[j][i + k];
opt[i][i + k] = j;
}
}
for (int j = opt[i + k - 1][i]; j <= opt[i + k][i + 1]; j++) {
if (ret[i + k][i] > lhs[i + k][j] + rhs[j][i]) {
ret[i + k][i] = lhs[i + k][j] + rhs[j][i];
opt[i + k][i] = j;
}
}
}
}
}
return ret;
}
vector<vector<int>> base_solve(int s, int e) {
auto ret = base_get(s);
for (int r = s + 1; r <= e; r++)
ret = mer(ret, base_get(r));
return ret;
}
}; // namespace DPHelper
class SegTree {
public:
int N{};
vector<vector<vector<int>>> vl;
SegTree() = default;
SegTree(int N) {
this->N = N;
vl.resize(N << 2);
}
void init(int s, int e, int n) {
if (e - s < L) {
vl[n] = DPHelper::base_solve(s, e);
return;
}
int m = (s + e) >> 1, k = n << 1;
init(s, m, k);
init(m + 1, e, k | 1);
vl[n] = DPHelper::mer(vl[k], vl[k | 1]);
}
inline void init() {
init(0, N - 1, 1);
}
void update(int s, int e, int n, int p) {
if (e < p || p < s) return;
if (e - s < L) {
vl[n] = DPHelper::base_solve(s, e);
return;
}
int m = (s + e) >> 1, k = n << 1;
update(s, m, k, p);
update(m + 1, e, k | 1, p);
vl[n] = DPHelper::mer(vl[k], vl[k | 1]);
}
inline void update(int p) {
update(0, N - 1, 1, p);
}
int query(int V1, int V2) {
return vl[1][V1][V2];
}
};
SegTree ST;
void init(int r, int c, int h[5000][200], int v[5000][200]) {
R = r, C = c;
H.resize(R);
V.resize(R - 1);
for (int i = 0; i < R; i++) copy(h[i], h[i] + C - 1, back_inserter(H[i]));
for (int i = 0; i < R - 1; i++) copy(v[i], v[i] + C, back_inserter(V[i]));
ST = SegTree(R);
ST.init();
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
ST.update(P);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
ST.update(P);
}
int escape(int V1, int V2) {
return ST.query(V1, V2);
}
