#include <bits/stdc++.h>
#include "wombats.h"
constexpr int LOG = 10;
constexpr int INF = 1000000000;
constexpr int RMAX = 5000;
constexpr int CMAX = 200;
constexpr int SEGMAX = 512;
bool chmin(int& x, const int y) {
if (x > y) {
x = y;
return true;
}
return false;
}
int R, C;
int hori[RMAX][CMAX], vert[RMAX][CMAX];
int size;
int dist[2 * SEGMAX][CMAX][CMAX];
int right[2 * SEGMAX];
int cumsum[CMAX];
int base[CMAX][CMAX], next[CMAX][CMAX];
int idx[CMAX][CMAX];
bool reached[2 * SEGMAX];
void setup(const int i) {
for (int j = 0; j < C - 1; ++j)
cumsum[j + 1] = cumsum[j] + hori[i][j];
for (int j = 0; j < C; ++j)
for (int k = 0; k < C; ++k)
base[j][k] = std::abs(cumsum[k] - cumsum[j]);
}
void absorb(const int i, const int m) {
for (int j = 0; j < C; ++j)
for (int k = 0; k < C; ++k)
next[j][k] = INF;
for (int j = 0; j < C; ++j)
for (int k = 0; k < C; ++k)
if (chmin(next[j][j], dist[i][j][k] + vert[m][k] + base[k][j]))
idx[j][j] = k;
for (int l = 1; l < C; ++l) {
for (int j = 0; j + l < C; ++j)
for (int k = idx[j][j + l - 1]; k <= idx[j + 1][j + l]; ++k)
if (chmin(next[j][j + l], dist[i][j][k] + vert[m][k] + base[k][j + l]))
idx[j][j + l] = k;
for (int j = l; j < C; ++j)
for (int k = idx[j - 1][j - l]; k <= idx[j][j - l + 1]; ++k)
if (chmin(next[j][j - l], dist[i][j][k] + vert[m][k] + base[k][j - l]))
idx[j][j - l] = k;
}
std::memcpy(dist[i], next, sizeof(dist[i]));
}
void fetch(const int k) {
if (reached[2 * k]) {
reached[k] = true;
std::memcpy(dist[k], dist[2 * k], sizeof(dist[k]));
right[k] = right[2 * k];
if (reached[2 * k + 1]) {
std::memcpy(base, dist[2 * k + 1], sizeof(base));
absorb(k, right[k]);
right[k] = right[2 * k + 1];
}
}
}
void update(int k) {
k += SEGMAX;
while (k > 1) {
k >>= 1;
fetch(k);
}
}
void recalc(const int i) {
const int up = LOG * i;
const int down = std::min(up + LOG, R);
setup(up);
std::memcpy(dist[SEGMAX + i], base, sizeof(dist[SEGMAX + i]));
right[SEGMAX + i] = down - 1;
for (int j = up + 1; j < down; ++j) {
setup(j);
absorb(SEGMAX + i, j - 1);
}
}
void init(int N, int M, int H[RMAX][CMAX], int V[RMAX][CMAX]) {
R = N, C = M;
for (int i = 0; i < R; ++i)
for (int j = 0; j < C - 1; ++j)
hori[i][j] = H[i][j];
for (int i = 0; i < R - 1; ++i)
for (int j = 0; j < C; ++j)
vert[i][j] = V[i][j];
size = (R + LOG - 1) / LOG;
for (int i = 0; i < size; ++i) {
recalc(i);
reached[SEGMAX + i] = true;
}
for (int i = SEGMAX - 1; i > 0; --i) {
fetch(i);
}
}
void changeH(int P, int Q, int W) {
hori[P][Q] = W;
recalc(P / LOG);
update(P / LOG);
}
void changeV(int P, int Q, int W) {
vert[P][Q] = W;
recalc(P / LOG);
update(P / LOG);
}
int escape(int V1, int V2) {
return dist[1][V1][V2];
}
