#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 9;
const int mxR = 5000;
const int mxC = 200;
const int bs = 20;
const int mxN = mxR / 20;
int h[mxR][mxC], v[mxR][mxC];
int H[mxN << 2], L[mxN << 2];
int opt[mxC + 1];
int nds[mxN << 2][mxC][mxC];
void build(int x, int lo, int hi) {
L[x] = lo; H[x] = hi;
if (lo == hi) {
return ;
}
int mid = (lo + hi) >> 1;
build(x << 1, lo, mid);
build(x << 1 | 1, mid + 1, hi);
}
void upd(int x, int l, int r) {
if (L[x] == H[x]) {
for (int i = 0; i < mxC; i++) {
for (int j = 0; j < mxC; j++) {
nds[x][i][j] = inf;
}
}
for (int j = 0; j < mxC; j++) {
nds[x][j][j] = 0;
for (int i = L[x] * bs; i < (L[x] + 1) * bs; i++) {
for (int k = 1; k < mxC; k++) {
nds[x][j][k] = min(nds[x][j][k], nds[x][j][k - 1] + h[i][k - 1]);
}
for (int k = mxC - 1; k; k--) {
nds[x][j][k - 1] = min(nds[x][j][k - 1], nds[x][j][k] + h[i][k - 1]);
}
for (int k = 0; k < mxC; k++) {
nds[x][j][k] += v[i][k];
}
}
}
return ;
}
if (l <= H[x << 1]) {
upd(x << 1, l, r);
}
if (H[x << 1] < r) {
upd(x << 1 | 1, l, r);
}
memset(opt, 0, mxC * 4);
for (int i = 0; i < mxC; i++) {
for (int j = mxC - 1; ~j; j--) {
array<int, 2> mn = {inf, 0};
for (int k = opt[j]; k <= opt[j + 1]; k++) {
mn = min(mn, {nds[x << 1][i][k] + nds[x << 1 | 1][k][j], -k});
}
nds[x][i][j] = mn[0];
opt[j] = -mn[1];
}
}
}
void init(int r, int c, int H[mxR][mxC], int V[mxR][mxC]) {
for (int i = 0; i < mxR; i++) {
for (int j = 0; j < mxC; j++) {
h[i][j] = inf;
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c - 1; j++) {
h[i][j] = H[i][j];
}
}
for (int i = 0; i < r - 1; i++) {
for (int j = 0; j < c; j++) {
v[i][j] = V[i][j];
}
}
opt[mxC] = mxC - 1;
build(1, 0, mxN - 1);
upd(1, 0, mxN - 1);
}
void changeH(int x, int y, int w) {
h[x][y] = w;
upd(1, x / bs, x / bs);
}
void changeV(int x, int y, int w) {
v[x][y] = w;
upd(1, x / bs, x / bs);
}
int escape(int x, int y) {
return nds[1][x][y];
}
/*
int main() {
cin.tie(0)->sync_with_stdio(0);
int r, c; cin >> r >> c;
int h[r][200], v[r][200];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c - 1; j++) {
cin >> h[i][j];
}
}
for (int i = 0; i < r - 1; i++) {
for (int j = 0; j < c; j++) {
cin >> v[i][j];
}
}
init(r, c, h, v);
int q; cin >> q;
while (q--) {
int type, x, y, w; cin >> type;
if (type == 3) {
cin >> x >> y;
cout << escape(x, y) << "\n";
}
else {
cin >> x >> y >> w;
//continue;
if (type == 1) {
changeH(x, y, w);
}
else {
changeV(x, y, w);
}
}
}
return 0;
}
*/
/*
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1
*/
