#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
static const int B = 10; // block size
static const int INF = 2e9;
int n, m;
int H[5000][200], Vv[5000][200];
// For Knuth optimization in merges
int opt_knuth[200][200];
// Each node stores an m×m matrix
using Mat = vector<array<int,200>>;
// Segment tree and mapping from block to leaf
vector<Mat> seg;
vector<int> which_leaf;
// Temporary matrices for building
Mat tmp1, tmp2;
// Build the single-row transfer matrix A from row i in O(m^2)
void build_row(int i, Mat &A) {
for(int j = 0; j < m; ++j) {
int sum = 0;
// move east
for(int k = j; k < m; ++k) {
A[j][k] = sum + Vv[i][k];
if (k+1 < m) sum += H[i][k];
}
sum = 0;
// move west
for(int k = j-1; k >= 0; --k) {
sum += H[i][k];
A[j][k] = sum + Vv[i][k];
}
}
}
// Knuth-optimized merge C = A ★ B in O(m^2)
void knuth_merge(const Mat &A, const Mat &B, Mat &C) {
// init to INF
for(int i = 0; i < m; ++i)
for(int j = 0; j < m; ++j)
C[i][j] = INF;
// traverse anti-diagonals
for(int dif = -(m-1); dif <= m-1; ++dif) {
int i0 = max(0, -dif);
int j0 = i0 + dif;
int len = min(m - i0, m - j0);
for(int t = 0; t < len; ++t) {
int i = i0 + t, j = j0 + t;
int lo = (j>0 ? opt_knuth[i][j-1] : 0);
int hi = (i+1<m ? opt_knuth[i+1][j] : m-1);
lo = max(lo, 0); hi = min(hi, m-1);
int best_k = lo;
int best_v = A[i][lo] + B[lo][j];
for(int k = lo+1; k <= hi; ++k) {
int v = A[i][k] + B[k][j];
if (v < best_v) {
best_v = v;
best_k = k;
}
}
C[i][j] = best_v;
opt_knuth[i][j] = best_k;
}
}
}
// Build the block-transfer matrix for block b into node seg[node_id]
void build_block(int b, int node_id) {
build_row(b*B, seg[node_id]);
int end = min((b+1)*B, n);
for(int i = b*B + 1; i < end; ++i) {
build_row(i, tmp1);
knuth_merge(seg[node_id], tmp1, tmp2);
seg[node_id] = tmp2;
}
}
// Build segment tree over blocks [l..r)
void build_tree(int node_id, int l, int r) {
if (r - l == 1) {
which_leaf[l] = node_id;
build_block(l, node_id);
} else {
int mid = (l + r) >> 1;
build_tree(2*node_id, l, mid);
build_tree(2*node_id + 1, mid, r);
knuth_merge(seg[2*node_id], seg[2*node_id + 1], seg[node_id]);
}
}
// Update block p (row i in block p has changed)
void update_tree(int node_id, int l, int r, int p) {
if (r - l == 1) {
build_block(p, node_id);
} else {
int mid = (l + r) >> 1;
if (p < mid)
update_tree(2*node_id, l, mid, p);
else
update_tree(2*node_id + 1, mid, r, p);
knuth_merge(seg[2*node_id], seg[2*node_id + 1], seg[node_id]);
}
}
// API
void init(int _n, int _m, int A[5000][200], int Bv[5000][200]) {
n = _n; m = _m;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j) {
H[i][j] = A[i][j];
Vv[i][j] = Bv[i][j];
}
int blocks = (n + B - 1) / B;
seg.resize(4 * blocks);
which_leaf.assign(blocks, -1);
tmp1.assign(m, array<int,200>());
tmp2.assign(m, array<int,200>());
build_tree(1, 0, blocks);
}
void changeH(int i, int j, int w) {
H[i][j] = w;
int b = i / B;
update_tree(1, 0, (n+B-1)/B, b);
}
void changeV(int i, int j, int w) {
Vv[i][j] = w;
int b = i / B;
update_tree(1, 0, (n+B-1)/B, b);
}
int escape(int v1, int v2) {
// root at seg[1] holds full n-row transfer
int ans = INF, sum = 0;
for(int k = v2; k < m; ++k) {
ans = min(ans, sum + seg[1][v1][k]);
if(k+1 < m) sum += H[n-1][k];
}
sum = 0;
for(int k = v2-1; k >= 0; --k) {
sum += H[n-1][k];
ans = min(ans, sum + seg[1][v1][k]);
}
return ans;
}
