#include "wombats.h"
#include "bits/stdc++.h"
#define here cerr<<"=======================================\n"
using ll = int;
using namespace std;
const ll maxn = 10005;
const ll maxh = 205;
const ll llinf = 2000000000;
ll n,m;
ll t[maxh][maxh][maxn], ls[maxn],rs[maxn];
ll a[maxn][maxh];
ll b[maxn][maxh];
ll tsz = 0,root = 0;
ll ps[maxh];
ll par[maxn];
ll ide[maxn];
void iit(ll &v,ll tl,ll tr) {
if(!v) v = ++tsz;
if(tl==tr) {
for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[tl][i-1];
for(ll i = 1;i<=m;i++) {
for(ll j = 1;j<=m;j++) t[i][j][v] = ps[max(i,j)]-ps[min(i,j)];
}
ide[tl] = v;
return;
}
ll mid = (tl+tr)/2;
iit(ls[v],tl,mid);
iit(rs[v],mid+1,tr);
for(ll i = 1;i<=m;i++) {
for(ll j = 1;j<=m;j++) {
t[i][j][v] = llinf;
for(ll k = 1;k<=m;k++) t[i][j][v] = min(t[i][j][v],t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k]);
}
}
par[mid] = v;
}
void upd(ll v,ll tl,ll tr,ll id) {
ll mid = (tl+tr)/2;
//cerr<<id<< " "<<v<< " "<<ls[v]<< " "<<rs[v]<<endl;
if(v==id) {
if(tl<tr) {
for(ll i = 1;i<=m;i++) {
for(ll j = 1;j<=m;j++) {
t[i][j][v] = llinf;
for(ll k = 1;k<=m;k++) t[i][j][v] = min(t[i][j][v],t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k]);
}
}
}else {
for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[tl][i-1];
for(ll i = 1;i<=m;i++) {
for(ll j = 1;j<=m;j++) t[i][j][v] = ps[max(i,j)]-ps[min(i,j)];
}
//cerr<<"A";
}
return;
}
if(id<rs[v]) upd(ls[v],tl,mid,id);
else upd(rs[v],mid+1,tr,id);
for(ll i = 1;i<=m;i++) {
for(ll j = 1;j<=m;j++) {
t[i][j][v] = llinf;
for(ll k = 1;k<=m;k++) t[i][j][v] = min(t[i][j][v],t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k]);
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R,m = C;
for(ll i = 1;i<=n;i++) {
for(ll j = 1;j<=m;j++) a[i][j] = H[i-1][j-1],b[i][j] = V[i-1][j-1];
}
iit(root,1,n);
}
void changeH(int P, int Q, int W) {
ll x = P+1,y = Q+1,w = W;
a[x][y] = w;
upd(root,1,n,ide[x]);
//cerr<<"B"<<endl;
}
void changeV(int P, int Q, int W) {
ll x = P+1,y = Q+1,w = W;
b[x][y] = w;
upd(root,1,n,par[x]);
}
int escape(int V1, int V2) {
V1++,V2++;
//cerr<<V1<< " "<<V2<<endl;
return t[V1][V2][root];
}
