#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 = 50;
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] = inf;
for(int i = 0;i<C;i++){
// cout << "root : " << l << " , " << i << endl;
bool vis[r-l+2][C];
memset(vis,0,sizeof(vis));
priority_queue < array<int,3> > pq;// dist , posx , posy
pq.push({0,l,i});
while(!pq.empty()){
auto tmp = pq.top();
pq.pop();
if(vis[tmp[1]-l][tmp[2]])continue;
// cout << tmp[1] << " " << tmp[2] << " : " << -tmp[0] << endl;
vis[tmp[1]-l][tmp[2]] = 1;
if(tmp[1] == r)
dist[i][tmp[2]] = min(dist[i][tmp[2]] , -tmp[0]);
if(tmp[1] < r and !vis[tmp[1]+1-l][tmp[2]])// asagi
pq.push({tmp[0] - V[tmp[1]][tmp[2]] , tmp[1]+1 , tmp[2]});
if(tmp[2] < C-1 and !vis[tmp[1]-l][tmp[2]+1])// saga
pq.push({tmp[0] - H[tmp[1]][tmp[2]] , tmp[1] , tmp[2]+1});
if(tmp[2] > 0 and !vis[tmp[1]-l][tmp[2]-1])// sola
pq.push({tmp[0] - H[tmp[1]][tmp[2]-1] , tmp[1] , tmp[2]-1});
}
}
}
friend Node merge(Node &a , Node &b , int split){
Node c;
int opt[200][200];
memset(opt , 0 , sizeof(opt));
for(int i=C-1;i>=0;i--){
for(int j = 0;j<C-i;j++){
int x = i+j , y = j;
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];
}
