/*
ID: varunra2
LANG: C++
TASK: wombat
*/
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
int n, m;
bool sub1 = false;
bool sub23 = false;
bool sub4 = false;
int hsh(int i, int j) { return i * m + j; }
PII unhsh(int h) { return MP(h / m, h % m); }
VVI h(5001, VI(201, INF));
VVI v(5001, VI(201));
const int block = 10;
const int c = 200;
void pr(int dp[c][c]) {
rep(i, 0, m) {
rep(j, 0, m) { cout << dp[i][j] << " "; }
cout << '\n';
}
cout << '\n';
}
struct node {
int dp[c][c];
VI opt;
void calcLeaf(int ind) {
for (int i = 0; i < c; i++) {
for (int j = 0; j < c; j++) {
dp[i][j] = INF;
}
}
for (int i = 0; i < c; i++) {
dp[i][i] = 0;
for (int j = ind * block; j < (ind + 1) * block; j++) {
for (int k = 1; k < c; k++) {
dp[i][k] = min(dp[i][k], dp[i][k - 1] + h[j][k - 1]);
}
for (int k = c - 1; k >= 1; k--) {
dp[i][k - 1] = min(dp[i][k - 1], dp[i][k] + h[j][k - 1]);
}
for (int k = 0; k < c; k++) {
dp[i][k] += v[j][k];
}
}
}
// cout << ind << '\n';
// pr(dp);
}
} segtree[1024];
void comb(node& a, node& l, node& r) {
a.opt.assign(c + 1, 0);
a.opt[c] = c - 1;
for (int i = 0; i < c; i++) {
for (int j = c - 1; j >= 0; j--) {
PII ret = MP(INF, 0);
for (int k = a.opt[j]; k <= a.opt[j + 1]; k++) {
ret = min(ret, MP(l.dp[i][k] + r.dp[k][j], -k));
}
a.dp[i][j] = ret.x;
a.opt[j] = -ret.y;
}
}
}
void upd(int l, int r, int tl, int tr, int node) {
if (l > tr or r < tl) return;
if (l == r) {
segtree[node].calcLeaf(l);
return;
}
int mid = (l + r) / 2;
upd(l, mid, tl, tr, 2 * node + 1);
upd(mid + 1, r, tl, tr, 2 * node + 2);
comb(segtree[node], segtree[2 * node + 1], segtree[2 * node + 2]);
}
const int siz = 500;
void upd(int l, int r) { upd(0, siz - 1, l, r, 0); }
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R;
m = C;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
h[i][j] = H[i][j];
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
v[i][j] = V[i][j];
}
}
upd(0, siz - 1);
// pr(segtree[0].dp);
}
void changeV(int p, int q, int w) {
v[p][q] = w;
upd(p / block, p / block);
}
void changeH(int p, int q, int w) {
h[p][q] = w;
upd(p / block, p / block);
}
int escape(int a, int b) { return segtree[0].dp[a][b]; }
// int main() {
// #ifndef ONLINE_JUDGE
// freopen("wombat.in", "r", stdin);
// freopen("wombat.out", "w", stdout);
// #endif
// cin.sync_with_stdio(0);
// cin.tie(0);
// int r, c;
// int h[5000][200];
// int v[5000][200];
// cin >> r >> c;
// rep(i, 0, r) rep(j, 0, c - 1) cin >> h[i][j];
// rep(i, 0, r - 1) rep(j, 0, c) cin >> v[i][j];
// init(r, c, h, v);
// debug("done");
// int q;
// cin >> q;
// while (q--) {
// int type;
// cin >> type;
// if (type == 0) {
// int a, b;
// cin >> a >> b;
// cout << escape(a, b) << '\n';
// } else if (type == 1) {
// int p, q, w;
// cin >> p >> q >> w;
// changeV(p, q, w);
// } else {
// int p, q, w;
// cin >> p >> q >> w;
// changeH(p, q, w);
// }
// debug("done", type);
// }
// return 0;
// }
