#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define vc vector
#define mins(a,b) (a=min(a,b))
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
int n, m, H[5000][200], V[5000][200], wh[5000];
vc<vc<vc<int>>> seg;
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(m3)
for(int i=0; i<m; i++)
fill(seg[id][i].begin(), seg[id][i].end(), 1e9);
for(int i=0; i<m; i++)
for(int j=0; j<m; j++)
for(int k=0; k<m; k++)
mins(seg[id][i][k], seg[lc][i][j]+seg[rc][j][k]);
}
void build(int l=0, int r=n-1, int id=1) { // O(nm3)
if(r-l == 1) {
wh[l] = id;
build_row(l);
return;
}
build(l, mid, lc);
build(mid, r, rc);
pull(id);
}
void upd(int p, int l=0, int r=n-1, int id=1) { // O(m3logn)
if(r-l == 1) {
build_row(p);
return;
}
p<mid ? upd(p, l, mid, lc) : upd(p, mid, r, rc);
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>>>(4*n+5, 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[1][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[1][v1][k]);
}
return ans;
}
