#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.begin();
#define all(x) x.begin(),x.end();
const int inf = 1e9 + 7;
const int BSZ = 20;
int R,C,H[5000][200],V[5000][200];
struct Node{
int dist[200][200];;
void update(int l , int r){
// cout << "update : " << l << " " << r << endl;
for(int i = 0;i<C;i++)
for(int j = 0;j<C;j++)
dist[i][j] = i == j ? 0 : inf;
for(int x = l;x<=r;x++){
int ndist[200][200];
for(int a = 0;a<C;a++){
int premax[C] , sufmax[C];
for(int i = 0;i<C;i++){
if(i == 0)
premax[i] = dist[a][i] + (x == l ? 0 : V[x-1][i]);
else
premax[i] = min(premax[i-1] + H[x][i-1] , dist[a][i] + (x == l ? 0 : V[x-1][i]));
}
for(int i = C-1;i>=0;i--){
if(i == C-1)
sufmax[i] = dist[a][i] + (x == l ? 0 : V[x-1][i]);
else
sufmax[i] = min(sufmax[i+1] + H[x][i] , dist[a][i] + (x == l ? 0 : V[x-1][i]));
}
for(int i = 0;i<C;i++){
ndist[a][i] = min(premax[i] , sufmax[i]);
}
}
for(int i = 0;i<200;i++)
for(int j = 0;j<200;j++)
dist[i][j] = ndist[i][j];
}
}
friend Node merge(Node &a , Node &b , int split){
Node c;
int opt[200][200];
memset(opt , 0 , sizeof(opt));
for(int x=C-1;x>=0;x--){
for(int y = 0;y<C;y++){
int lo = y == 0 ? 0 : opt[x][y-1];
int hi = x == C-1 ? C-1 : opt[x+1][y];
for(int k = lo;k<=hi;k++)
if(a.dist[x][opt[x][y]] + V[split][opt[x][y]] + b.dist[opt[x][y]][y] > a.dist[x][k] + V[split][k] + b.dist[k][y])
opt[x][y] = k;
}
}
for(int i = 0;i<C;i++)
for(int j = 0;j<C;j++)
c.dist[i][j] = a.dist[i][opt[i][j]] + V[split][opt[i][j]] + b.dist[opt[i][j]][j];
return c;
}
} tree[4*(5000/BSZ + 7)];
void build(int ind , int l , int r){
// cout << "build : " << ind << " " << l << " " << r << endl;
if(l == r){
tree[ind].update(l * BSZ , min(R,(l+1)*BSZ)-1);
// cout << "block : " << l << endl;
// for(int i = 0;i<C;i++){
// for(int j = 0;j<C;j++){
// cout << tree[ind].dist[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
return;
}
int mid = (l + r) / 2;
build(ind*2,l,mid);
build(ind*2+1,mid+1,r);
tree[ind] = merge(tree[ind*2] , tree[ind*2+1] , (mid+1)*BSZ-1);
// cout << l << " " << r << " : " << (mid+1)*BSZ-1 << endl;
}
void update(int pos , int ind , int l , int r){
if(l == r){
tree[ind].update(l * BSZ , min(R,(l+1)*BSZ)-1);
return;
}
int mid = (l + r) / 2;
if(pos <= mid)update(pos,ind*2,l,mid);
else update(pos,ind*2+1,mid+1,r);
tree[ind] = merge(tree[ind*2] , tree[ind*2+1] , (mid+1)*BSZ-1);
}
void init(int iR, int iC, int iH[5000][200], int iV[5000][200]) {
// cout << "flag0" << endl;
R = iR , C = iC;
for(int i = 0;i<5000;i++){
for(int j = 0;j<200;j++){
H[i][j] = iH[i][j];
V[i][j] = iV[i][j];
}
}
// cout << "flag1" << endl;
build(1,0,(R+BSZ-1)/BSZ-1);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
update(P/BSZ , 1 , 0 , (R+BSZ-1)/BSZ-1);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
update(P/BSZ , 1 , 0 , (R+BSZ-1)/BSZ-1);
}
int escape(int V1, int V2) {
return tree[1].dist[V1][V2];
}
