#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)
const int B = 10;
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];
inline void merge(vc<vc<int>> &A, vc<vc<int>> &B, vc<vc<int>> &C) { // O(m2)
for(int i=0; i<m; i++)
fill(C[i].begin(), C[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(A[i][k]+B[k][j]<C[i][j]) {
opt[i][j] = k;
C[i][j] = A[i][k] + B[k][j];
}
}
inline void build_row(int i, vc<vc<int>> &A) { // O(m2)
for(int j=0; j<m; j++) {
for(int k=j, sum=0; k<m; k++) {
A[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];
A[j][k] = sum + V[i][k];
}
}
}
vc<vc<int>> tmp1, tmp2;
inline void build_block(int b) { // O(Bm2)
build_row(b*B, seg[wh[b]]);
for(int i=b*B+1; i<(b+1)*B && i+1<n; i++) {
build_row(i, tmp1);
merge(seg[wh[b]], tmp1, tmp2);
seg[wh[b]] = tmp2;
}
}
void build(int l=0, int r=(n+B-1)/B, int id=0) { // O(nm2)
if(r-l == 1) {
wh[l] = id;
build_block(l);
return;
}
lc[id] = ++N;
rc[id] = ++N;
build(l, mid, lc[id]);
build(mid, r, rc[id]);
merge(seg[lc[id]], seg[rc[id]], seg[id]);
}
void upd(int p, int l=0, int r=(n+B-1)/B, int id=0) { // O(Bm2logn)
if(r-l == 1) {
build_block(p);
return;
}
p<mid ? upd(p, l, mid, lc[id]) : upd(p, mid, r, rc[id]);
merge(seg[lc[id]], seg[rc[id]], seg[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+::B-1)/::B)-1, vc<vc<int>>(m, vc<int>(m)));
tmp1 = vc<vc<int>>(m, vc<int>(m));
tmp2 = vc<vc<int>>(m, vc<int>(m));
build();
}
void changeH(int i, int j, int w) {
H[i][j] = w;
upd(i/B);
}
void changeV(int i, int j, int w) {
V[i][j] = w;
upd(i/B);
}
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;
}
