#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/2][maxh];
ll b[maxn/2][maxh];
ll tsz = 0,root = 0;
ll ps[maxh];
ll pre[maxn/2];
ll ide[maxn/2];
ll opt[maxh][maxh];
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 = 0;i<=m+1;i++) for(ll j = 0;j<=m+1;j++) opt[i][j] = -1;
for(ll len = 0;len<=m-1;len++) {
for(ll i = 1;i+len<=m;i++) {
ll j = i+len;
ll lb = opt[i][j-1]!=-1?opt[i][j-1]:1;
ll rb = opt[i+1][j]!=-1?opt[i+1][j]:m;
t[i][j][v] = llinf;
for(ll k = lb;k<=rb;k++) {
ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
if(cur<t[i][j][v]) {
t[i][j][v] = cur;
opt[i][j] = k;
}
}
}
}
for(ll len = 0;len<=m-1;len++) {
for(ll i = m;i>=len+1;i--) {
ll j = i-len;
ll lb = opt[i-1][j]!=-1?opt[i-1][j]:1;
ll rb = opt[i][j+1]!=-1?opt[i][j+1]:m;
t[i][j][v] = llinf;
for(ll k = lb;k<=rb;k++) {
ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
if(cur<t[i][j][v]) {
t[i][j][v] = cur;
opt[i][j] = k;
}
}
}
}
pre[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 = 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)];
}
return;
}else {
for(ll i = 0;i<=m+1;i++) for(ll j = 0;j<=m+1;j++) opt[i][j] = -1;
for(ll len = 0;len<=m-1;len++) {
for(ll i = 1;i+len<=m;i++) {
ll j = i+len;
ll lb = opt[i][j-1]!=-1?opt[i][j-1]:1;
ll rb = opt[i+1][j]!=-1?opt[i+1][j]:m;
t[i][j][v] = llinf;
for(ll k = lb;k<=rb;k++) {
ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
if(cur<t[i][j][v]) {
t[i][j][v] = cur;
opt[i][j] = k;
}
}
}
}
for(ll len = 0;len<=m-1;len++) {
for(ll i = m;i>=len+1;i--) {
ll j = i-len;
ll lb = opt[i-1][j]!=-1?opt[i-1][j]:1;
ll rb = opt[i][j+1]!=-1?opt[i][j+1]:m;
t[i][j][v] = llinf;
for(ll k = lb;k<=rb;k++) {
ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
if(cur<t[i][j][v]) {
t[i][j][v] = cur;
opt[i][j] = k;
}
}
}
}
//cerr<<"A";
}
return;
}
if(id<rs[v]) upd(ls[v],tl,mid,id);
else upd(rs[v],mid+1,tr,id);
for(ll i = 0;i<=m+1;i++) for(ll j = 0;j<=m+1;j++) opt[i][j] = -1;
for(ll len = 0;len<=m-1;len++) {
for(ll i = 1;i+len<=m;i++) {
ll j = i+len;
ll lb = opt[i][j-1]!=-1?opt[i][j-1]:1;
ll rb = opt[i+1][j]!=-1?opt[i+1][j]:m;
t[i][j][v] = llinf;
for(ll k = lb;k<=rb;k++) {
ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
if(cur<t[i][j][v]) {
t[i][j][v] = cur;
opt[i][j] = k;
}
}
}
}
for(ll len = 0;len<=m-1;len++) {
for(ll i = m;i>=len+1;i--) {
ll j = i-len;
ll lb = opt[i-1][j]!=-1?opt[i-1][j]:1;
ll rb = opt[i][j+1]!=-1?opt[i][j+1]:m;
t[i][j][v] = llinf;
for(ll k = lb;k<=rb;k++) {
ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
if(cur<t[i][j][v]) {
t[i][j][v] = cur;
opt[i][j] = k;
}
}
}
}
// cerr<<id<< " "<<v<< " "<<ls[v]<< " "<<rs[v]<<" "<<222222<<endl;
}
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,pre[x]);
}
int escape(int V1, int V2) {
V1++,V2++;
//cerr<<V1<< " "<<V2<<endl;
return t[V1][V2][root];
}
