#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
const int INF=1e9;
int r,c;
int h[5005][205];
int v[5005][205];
int data[17000][105][105];
int pre[205]; //save space ig
void build(int u,int pos){
for (int x=1;x<c;x++){
pre[x]=pre[x-1]+h[pos][x-1];
}
for (int x=0;x<c;x++){
for (int y=0;y<c;y++){
data[u][x][y]=pre[max(x,y)]-pre[min(x,y)]+v[pos][y];
}
}
}
void merge(int u){
int l=u<<1,r=u<<1|1;
for (int x=0;x<c;x++){
for (int y=0;y<c;y++){
data[u][x][y]=INF;
for (int z=0;z<c;z++){
data[u][x][y]=min(data[u][x][y],data[l][x][z]+data[r][z][y]);
}
}
}
}
void init(int u,int s,int e){
if (s==e){
build(u,s);
}
else{
int m=s+e>>1;
init(u<<1,s,m);
init(u<<1|1,m+1,e);
merge(u);
}
}
void update(int u,int i,int s,int e){
if (s==e){
build(u,s);
}
else{
int m=s+e>>1;
if (i<=m) update(u<<1,i,s,m);
else update(u<<1|1,i,m+1,e);
merge(u);
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r=R,c=C;
for (int x=0;x<r;x++){
for (int y=0;y<c-1;y++){
h[x][y]=H[x][y];
}
}
for (int x=0;x<r-1;x++){
for (int y=0;y<c;y++){
v[x][y]=V[x][y];
}
}
init(1,0,r-1);
}
void changeH(int P, int Q, int W) {
h[P][Q]=W;
update(1,P,0,r-1);
}
void changeV(int P, int Q, int W) {
v[P][Q]=W;
update(1,P,0,r-1);
}
int escape(int c1, int c2) {
return data[1][c1][c2];
}
