#include <bits/stdc++.h>
#include "wombats.h"
template <class T> using Vec = std::vector<T>;
namespace solver {
constexpr int LOG = 13;
constexpr int INF = 1000000000;
struct Data {
Vec<Vec<int>> dist;
int right;
Data(): dist(), right() {}
};
int R, C;
Vec<Vec<int>> hori, vert;
Vec<Data> seg;
void set_size(const int s) {
int t = 1;
while (t < s) t <<= 1;
seg.resize(2 * t);
}
Vec<Vec<int>> calc_row(const int i) {
Vec<Vec<int>> ret(C, Vec<int>(C));
Vec<int> sum(C);
for (int j = 0; j < C - 1; ++j) {
sum[j + 1] = sum[j] + hori[i][j];
}
for (int j = 0; j < C; ++j) {
for (int k = j + 1; k < C; ++k) {
ret[j][k] = ret[k][j] = sum[k] - sum[j];
}
}
return ret;
}
bool setmin(int &x, const int y) {
if (x > y) {
x = y;
return true;
}
return false;
}
void absorb(Vec<Vec<int>>& cur, const int i, const Vec<Vec<int>>& add) {
Vec<Vec<int>> idx(C, Vec<int>(C));
Vec<Vec<int>> next(C, Vec<int>(C, INF));
for (int j = 0; j < C; ++j) {
for (int k = 0; k < C; ++k) {
if (setmin(next[j][j], cur[j][k] + vert[i][k] + add[k][j])) {
idx[j][j] = k;
}
}
}
for (int width = 1; width < C; ++width) {
for (int j = 0; j + width < C; ++j) {
for (int k = idx[j][j + width - 1]; k <= idx[j + 1][j + width]; ++k) {
if (setmin(next[j][j + width], cur[j][k] + vert[i][k] + add[k][j + width])) {
idx[j][j + width] = k;
}
}
}
for (int j = width; j < C; ++j) {
for (int k = idx[j - 1][j - width]; k <= idx[j][j - width + 1]; ++k) {
if (setmin(next[j][j - width], cur[j][k] + vert[i][k] + add[k][j - width])) {
idx[j][j - width] = k;
}
}
}
}
cur = std::move(next);
}
void recalc(const int sec) {
const int left = LOG * sec;
const int right = std::min(left + LOG, R);
auto& data = seg[sec + seg.size() / 2];
data.dist = calc_row(left);
data.right = left;
for (int i = left + 1; i < right; ++i) {
absorb(data.dist, data.right, calc_row(i));
data.right += 1;
}
}
void fetch(const int k) {
seg[k].dist = seg[2 * k].dist;
if (!seg[2 * k + 1].dist.empty()) {
absorb(seg[k].dist, seg[k].right, seg[2 * k + 1].dist);
seg[k].right = seg[2 * k + 1].right;
}
}
void update(int k) {
k += (int) seg.size() / 2;
while (k > 1) {
k >>= 1;
fetch(k);
}
}
};
void init(int N, int M, int H[5000][200], int V[5000][200]) {
using namespace solver;
R = N;
C = M;
hori = Vec<Vec<int>>(R, Vec<int>(C - 1));
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C - 1; ++j) {
hori[i][j] = H[i][j];
}
}
vert = Vec<Vec<int>>(R - 1, Vec<int>(C));
for (int i = 0; i < R - 1; ++i) {
for (int j = 0; j < C; ++j) {
vert[i][j] = V[i][j];
}
}
const int size = (R + LOG - 1) / LOG;
set_size(size);
for (int i = 0; i < size; ++i) {
recalc(i);
}
for (int i = (int) seg.size() / 2 - 1; i > 0; --i) {
fetch(i);
}
}
void changeH(int P, int Q, int W) {
using namespace solver;
hori[P][Q] = W;
recalc(P / LOG);
update(P / LOG);
}
void changeV(int P, int Q, int W) {
using namespace solver;
vert[P][Q] = W;
recalc(P / LOG);
update(P / LOG);
}
int escape(int V1, int V2) {
using namespace solver;
return seg[1].dist[V1][V2];
}
