#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define vc vector
#define mins(a,b) (a=min(a,b))
#define mid ((l+r)>>1)
int n, m, H[5000][200], V[5000][200], wh[5000], N, lc[10000], rc[10000];
vc<vc<vc<int>>> seg;
int opt[200][200];
void build_row(int i) { // O(m2)
for(int j=0; j<m; j++) {
for(int k=j, sum=0; k<m; k++) {
seg[wh[i]][j][k] = sum + V[i][k];
if(k+1<m) sum += H[i][k];
}
for(int k=j-1, sum=0; k>=0; k--) {
sum += H[i][k];
seg[wh[i]][j][k] = sum + V[i][k];
}
}
}
inline void pull(int id) { // O(m2)
for(int i=0; i<m; i++)
fill(seg[id][i].begin(), seg[id][i].end(), 2e9);
for(int dif=-(m-1); dif<=(m-1); dif++)
for(int i=max(-dif, 0), j=i+dif; i<m && j<m; i++, j++)
for(int k=(j ? opt[i][j-1] : 0); k<=(i+1<m ? opt[i+1][j] : m-1); k++)
if(seg[lc[id]][i][k]+seg[rc[id]][k][j]<seg[id][i][j]) {
opt[i][j] = k;
seg[id][i][j] = seg[lc[id]][i][k] + seg[rc[id]][k][j];
}
}
void build(int l=0, int r=n-1, int id=0) { // O(nm2)
if(r-l == 1) {
wh[l] = id;
build_row(l);
return;
}
lc[id] = ++N;
rc[id] = ++N;
build(l, mid, lc[id]);
build(mid, r, rc[id]);
pull(id);
}
void upd(int p, int l=0, int r=n-1, int id=0) { // O(m2logn)
if(r-l == 1) {
build_row(p);
return;
}
p<mid ? upd(p, l, mid, lc[id]) : upd(p, mid, r, rc[id]);
pull(id);
}
void init(int n, int m, int A[5000][200], int B[5000][200]) {
::n = n;
::m = m;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
H[i][j] = A[i][j],
V[i][j] = B[i][j];
seg = vc<vc<vc<int>>>(2*n-1, vc<vc<int>>(m, vc<int>(m, 0)));
build();
}
void changeH(int i, int j, int w) {
H[i][j] = w;
upd(i);
}
void changeV(int i, int j, int w) {
V[i][j] = w;
upd(i);
}
int escape(int v1, int v2) {
int ans = 1e9;
for(int k=v2, sum=0; k<m; k++) {
ans = min(ans, sum + seg[0][v1][k]);
if(k+1<m) sum += H[n-1][k];
}
for(int k=v2-1, sum=0; k>=0; k--) {
sum += H[n-1][k];
ans = min(ans, sum + seg[0][v1][k]);
}
return ans;
}
