#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
int R, C;
static int h[5000][200], v_cost[5000][200];
// A C×C matrix of ll
struct Mat {
vector<vector<ll>> a;
Mat(int C_=0, ll val = INF): a(C_, vector<ll>(C_, val)) {}
};
// per-row transfer matrices
vector<Mat> M; // size R-1
// segment tree of size ~4R
vector<Mat> seg;
// compute M[i] in O(C^2)
void build_row(int i) {
Mat &m = M[i];
for(int a = 0; a < C; ++a) {
static ll dist[200];
// init
for(int j = 0; j < C; ++j) dist[j] = INF;
dist[a] = 0;
// left→right
for(int j = 1; j < C; ++j)
dist[j] = min(dist[j], dist[j-1] + h[i][j-1]);
// right→left
for(int j = C-2; j >= 0; --j)
dist[j] = min(dist[j], dist[j+1] + h[i][j]);
// fill M[i][a][b]
for(int b = 0; b < C; ++b)
m.a[a][b] = dist[b] + v_cost[i][b];
}
}
// min-plus multiply A⋆B, both C×C, in O(C^3)
Mat multiply(const Mat &A, const Mat &B) {
Mat Rmat(C);
for(int i = 0; i < C; ++i) {
for(int k = 0; k < C; ++k) {
ll v = A.a[i][k];
if (v >= INF) continue;
for(int j = 0; j < C; ++j) {
Rmat.a[i][j] = min(Rmat.a[i][j], v + B.a[k][j]);
}
}
}
return Rmat;
}
// build segtree on [l..r)
void build_seg(int idx, int l, int r) {
if (r - l == 1) {
seg[idx] = M[l];
} else {
int mid = (l + r) >> 1;
build_seg(idx*2, l, mid);
build_seg(idx*2+1, mid, r);
seg[idx] = multiply(seg[idx*2], seg[idx*2+1]);
}
}
// point-update M[pos], then refresh tree
void update_seg(int idx, int l, int r, int pos) {
if (r - l == 1) {
seg[idx] = M[pos];
} else {
int mid = (l + r) >> 1;
if (pos < mid) update_seg(idx*2, l, mid, pos);
else update_seg(idx*2+1, mid, r, pos);
seg[idx] = multiply(seg[idx*2], seg[idx*2+1]);
}
}
// query product on [ql..qr)
Mat query_seg(int idx, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return seg[idx];
int mid = (l + r) >> 1;
if (qr <= mid) return query_seg(idx*2, l, mid, ql, qr);
if (ql >= mid) return query_seg(idx*2+1, mid, r, ql, qr);
Mat left = query_seg(idx*2, l, mid, ql, qr);
Mat right = query_seg(idx*2+1, mid, r, ql, qr);
return multiply(left, right);
}
// API
void init(int R_, int C_,
int H_in[5000][200],
int V_in[5000][200]) {
R = R_; C = C_;
// copy data
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
h[i][j] = (j < C-1 ? H_in[i][j] : 0);
v_cost[i][j] = (i < R-1 ? V_in[i][j] : 0);
}
}
// allocate
M.assign(R-1, Mat(C));
seg.assign(4*(R-1), Mat(C));
// build rows + segtree
for (int i = 0; i < R-1; ++i)
build_row(i);
build_seg(1, 0, R-1);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
// rebuild row P
build_row(P);
update_seg(1, 0, R-1, P);
}
void changeV(int P, int Q, int W) {
v_cost[P][Q] = W;
// rebuild row P
build_row(P);
update_seg(1, 0, R-1, P);
}
int escape(int V1, int V2) {
// query full product M[0]⋆⋯⋆M[R-2]
Mat Mtot = query_seg(1, 0, R-1, 0, R-1);
// entry [V1][V2]
return (int)Mtot.a[V1][V2];
}
