#include "wombats.h"
#include <bits/stdc++.h>
#define R 5005
#define C 205
using namespace std;
const int block = 40;
int r,c;
int h[R][C];
int w[R][C];
int opt[C][C];
struct node{
int a[C][C];
int l,r;
node(int init){
for(int i = 0;i<C;i++){
for(int j = 0;j<C;j++){
a[i][j] = init;
}
}
}
}tmp(0);
node merge(node a,node b){
for(int dif = -c-1;dif < c ;dif++){
for(int i = max(0,-dif);i + max(0,dif)<c;i++){
int j = dif + i;
int l = 0,r = c-1;
if(j)
l = opt[i][j-1];
if(i + 1 != c)
r = opt[i+1][j];
tmp.a[i][j] = 1e9;
for(int x = l;x<=r;x++){
if(a.a[i][x] + b.a[x][j] < tmp.a[i][j]){
tmp.a[i][j] = a.a[i][x] + b.a[x][j];
opt[i][j] = x;
}
}
}
}
return tmp;
}
struct SegTree{
vector<node> t;
int n;
void init(int size){
n = size;
t.assign(4*n + 5,1e9);
build(1,0,n-1);
}
void build(int v,int tl,int tr){
t[v].l = tl * block;
t[v].r = min(r-1,(tr + 1) * block - 1);
if(tl == tr){
for(int i = 0;i<c;i++){
t[v].a[i][i] = 0;
for(int j = t[v].l;j<=t[v].r;j++){
for(int d=1;d<c;d++){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d-1] + h[j][d-1]);
}
for(int d=c-2;d>=0;d--){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d+1] + h[j][d]);
}
for(int d=0;d<c;d++){
t[v].a[i][d] = t[v].a[i][d] + w[j][d];
}
}
}
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v] = merge(t[v*2],t[v*2+1]);
}
void upd(int v,int tl,int tr,int pos){
if(tl == tr){
for(int i = 0;i<c;i++){
t[v].a[i][i] = 0;
for(int j = t[v].l;j<=t[v].r;j++){
for(int d=1;d<c;d++){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d-1] + h[j][d-1]);
}
for(int d=c-2;d>=0;d--){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d+1] + h[j][d]);
}
for(int d=0;d<c;d++){
t[v].a[i][d] = t[v].a[i][d] + w[j][d];
}
}
}
return;
}
int tm = (tl + tr)/2;
if(pos <= tm)
upd(v*2,tl,tm,pos);
else upd(v*2+1,tm+1,tr,pos);
t[v] = merge(t[v*2],t[v*2+1]);
}
void upd(int pos){
upd(1,0,n-1,pos);
}
}tree;
void init(int r_, int c_, int h_[5000][200], int v_[5000][200]) {
r = r_;
c = c_;
for(int i = 0;i<r;i++){
for(int j = 0;j<c;j++){
h[i][j] = h_[i][j];
w[i][j] = v_[i][j];
}
}
tree.init((r+block-1) / block);
}
void changeH(int p, int q, int x) {
h[p][q] = x;
tree.upd(p/block);
}
void changeV(int p, int q, int x) {
w[p][q] = x;
if(p % block == 0 && p)
tree.upd(p/block - 1);
tree.upd(p/block);
}
int escape(int v1, int v2) {
return tree.t[1].a[v1][v2];
}
