#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF = 2e9 + 100;
int (*H)[200], (*V)[200], n, m;
int sum[5000][200];
inline int dist(int x, int i, int j){
if (i<=j) return sum[x][j] - sum[x][i];
return sum[x][i] - sum[x][j];
}
struct Node{
int a[101][101];
Node(){}
void init(int x){
for (int i=0;i<m;i++){
for (int j=0;j<m;j++){
a[i][j] = INF;
for (int k=0;k<m;k++){
a[i][j] = min(a[i][j], V[x][k] + dist(x, i, k) + dist(x+1, j, k));
}
// printf("%d %d %d -> %d\n", x, i, j, a[i][j]);
}
}
}
void merge(const Node &L, const Node &R){
for (int i=0;i<m;i++){
for (int j=0;j<m;j++){
a[i][j] = INF;
for (int k=0;k<m;k++){
a[i][j] = min(a[i][j], L.a[i][k] + R.a[k][j]);
}
}
}
}
};
struct Seg{
Node tree[20020];
void init(int i, int l, int r){
if (l==r){
tree[i].init(l);
return;
}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i].merge(tree[i<<1], tree[i<<1|1]);
}
void update(int i, int l, int r, int p){
if (r<p || p<l) return;
if (l==r){
tree[i].init(l);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, p); update(i<<1|1, m+1, r, p);
tree[i].merge(tree[i<<1], tree[i<<1|1]);
}
}tree;
void initH(int x){
for (int i=1;i<m;i++) sum[x][i] = sum[x][i-1] + H[x][i-1];
}
void init(int R, int C, int h[5000][200], int v[5000][200]) {
n = R, m = C;
H = h, V = v;
for (int i=0;i<R;i++) initH(i);
tree.init(1, 0, n-2);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
initH(P);
tree.update(1, 0, n-2, P-1);
tree.update(1, 0, n-2, P);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
tree.update(1, 0, n-2, P);
}
int escape(int V1, int V2) {
return tree.tree[1].a[V1][V2];
}
