#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class segTree {
public:
void init(int sz) {
this->sz = sz;
T.resize(4 * sz + 7);
}
int query(int c1, int c2) {
return T[0].mat[c1][c2];
}
void update(int pos, int v1, int v2, int h) {
update(0, 0, sz - 1, pos, v1, v2, h);
}
private:
struct node {
vector < vector < int > > mat;
node(int v1, int v2, int h) {
mat.resize(2, vector < int >(2, 0));
mat[0][0] = v1;
mat[0][1] = v1 + h;
mat[1][0] = v2 + h;
mat[1][1] = v2;
}
node() {
mat.resize(2, vector < int >(2, 0));
}
};
node combine(node v1, node v2) {
node res;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
res.mat[i][j] = min(v1.mat[i][0] + v2.mat[0][j], v1.mat[i][1] + v2.mat[1][j]);
}
}
return res;
}
void update(int val, int tl, int tr, int pos, int v1, int v2, int h) {
if(tl == tr) {
T[val] = {v1, v2, h};
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) update(2 * val + 1, tl, tm, pos, v1, v2, h);
else update(2 * val + 2, tm + 1, tr, pos, v1, v2, h);
T[val] = combine(T[2 * val + 1], T[2 * val + 2]);
}
int sz;
vector < node > T;
}t;
int r, c, sum;
vector < vector < int > > h, v;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R; c = C;
h.resize(r, vector < int >(c));
v.resize(r, vector < int >(c));
sum = 0;
for(int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
h[i][j] = H[i][j];
v[i][j] = V[i][j];
sum += V[i][j];
}
}
if(c == 2) {
t.init(r);
for(int i = 0; i < r; i++) {
if(i == 0) {
t.update(i, 0, 0, h[i][0]);
continue;
}
t.update(i, v[i - 1][0], v[i - 1][1], h[i][0]);
}
}
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
if(c == 2) {
t.update(P, v[P - 1][0], v[P - 1][1], h[P][0]);
}
}
void changeV(int P, int Q, int W) {
if(c == 1) sum += W - v[P][Q];
v[P][Q] = W;
if(c == 2) {
t.update(P + 1, v[P][0], v[P][1], h[P + 1][0]);
}
}
int escape(int v1, int v2) {
if(c == 1) {
return sum;
}
if(c == 2) {
return t.query(v1, v2);
}
vector < vector < int > > F(r, vector < int >(c, INF));
vector < vector < int > > p(r, vector < int >(c, 0));
for(int i = 0; i < r; i++) {
for(int j = 1; j < c; j++) {
p[i][j] = h[i][j - 1] + p[i][j - 1];
}
}
for(int i = 0; i < v1; i++) F[0][i] = p[0][v1] - p[0][i];
for(int i = v1; i < c; i++) F[0][i] = p[0][i] - p[0][v1];
for(int i = 1; i < r; i++) {
int mi = INF;
for(int j = 0; j < c; j++) {
mi = min(mi, F[i - 1][j] + v[i - 1][j] - p[i][j]);
F[i][j] = min(F[i][j], mi + p[i][j]);
}
mi = INF;
for(int j = c - 1; j >= 0; j--) {
mi = min(mi, F[i - 1][j] + v[i - 1][j] + p[i][j]);
F[i][j] = min(F[i][j], mi - p[i][j]);
}
}
return F[r - 1][v2];
}
