#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 7;
const int M = 200 + 7;
const int INF = (int) 1e9 + 7;
const int BUCKETSIZE = 10;
int H[N][M];
int V[N][M];
int n;
int m;
struct Node {
int l;
int r;
vector<vector<int>> cost;
Node() :
l(0),
r(0),
cost(m, vector<int> (m, INF)) {
}
};
vector<Node> tree;
void placeSmall(Node &guy, int l, int r) {
guy.l = l;
guy.r = r;
for (int start = 0; start < m; start++) {
for (int col = 0; col < m; col++) {
guy.cost[start][col] = INF;
}
guy.cost[start][start] = 0;
for (int col = 1; col < m; col++) {
guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col - 1] + H[l][col - 1]);
}
for (int col = m - 2; col >= 0; col--){
guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col + 1] + H[l][col]);
}
}
for (int row = l + 1; row <= r; row++) {
/// add row j
for (int start = 0; start < m; start++) {
for (int col = 0; col < m; col++) {
guy.cost[start][col] += V[row - 1][col];
}
for (int col = 1; col < m; col++) {
guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col - 1] + H[row][col - 1]);
}
for (int col = m - 2; col >= 0; col--){
guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col + 1] + H[row][col]);
}
}
}
}
int A[M][M];
int B[M][M];
int opt[M][M];
void join(Node& solution, Node& lft, Node& rgh) {
solution.l = lft.l;
solution.r = rgh.r;
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
A[i][j] = lft.cost[i][j] + V[lft.r][j];
B[i][j] = rgh.cost[i][j];
solution.cost[i][j] = INF;
opt[i][j] = -1;
}
}
for (int i = 0; i < m; i++) {
for (int k = m - 1; k >= 0; k--) {
int nd = m - 1, st = 0;
if (k + 1 < m) {
nd = opt[i][k + 1];
}
if (i - 1 >= 0) {
st = opt[i - 1][k];
}
for (int j = st; j <= nd; j++) {
if (A[i][j] + B[j][k] < solution.cost[i][k]) {
solution.cost[i][k] = A[i][j] + B[j][k];
opt[i][k] = j;
}
}
}
}
}
void update(int v, int tl, int tr, int pos) {
int LEN = tr - tl + 1;
if (LEN <= BUCKETSIZE) {
placeSmall(tree[v], tl, tr);
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(2 * v, tl, tm, pos);
} else {
update(2 * v + 1, tm + 1, tr, pos);
}
join(tree[v], tree[2 * v], tree[2 * v + 1]);
}
void build(int v, int tl, int tr) {
while (v >= (int) tree.size()) tree.push_back({});
if (tr - tl + 1 <= BUCKETSIZE) {
placeSmall(tree[v], tl, tr);
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
join(tree[v], tree[2 * v], tree[2 * v + 1]);
}
void init(int R, int C, int Hinit[5000][200], int Vinit[5000][200]) {
n = R;
m = C;
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) H[i][j] = Hinit[i][j], V[i][j] = Vinit[i][j];
build(1, 0, n - 1);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
update(1, 0, n - 1, P);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
update(1, 0, n - 1, P);
}
int escape(int V1, int V2) {
return tree[1].cost[V1][V2];
}
