#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxr = 5005;
const int maxc = 205;
const int INF = 1e9+5;
int pos[maxc][maxc];
int n, m;
int WH[maxr][maxc];
int WV[maxr][maxc];
struct matrix{
int a[maxc][maxc];
matrix(){}
matrix operator*(const matrix &rhs){
matrix re;
for(int d = m-1; d >= 0; d--){
for(int i = 0; i+d < m; i++){
int j = i + d, l, r;
re.a[i][j] = INF;
if(i == 0)l = 0;
else l = pos[i-1][j];
if(j == m-1)r = m-1;
else r = m-1;
for(int k = l; k <= r; k++){
if(a[i][k] + rhs.a[k][j] < re.a[i][j]){
re.a[i][j] = a[i][k] + rhs.a[k][j];
pos[i][j] = k;
}
}
}
}
for(int d = m-1; d > 0; d--){
for(int j = 0; j+d < m; j++){
int i = j + d, l, r;
re.a[i][j] = INF;
if(j == 0)l = 0;
else l = pos[i][j-1];
if(i == m-1)r = m-1;
else r = pos[i+1][j];
for(int k = l; k <= r; k++){
if(a[i][k] + rhs.a[k][j] < re.a[i][j]){
re.a[i][j] = a[i][k] + rhs.a[k][j];
pos[i][j] = k;
}
}
}
}
return re;
}
matrix(int l, int r){
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
a[i][j] = (i == j ? 0 : INF);
}
}
for(int k = l; k <= r; k++){
for(int i = 0; i < m; i++){
for(int j = 1; j < m; j++){
a[i][j] = min(a[i][j], a[i][j-1] + WH[k][j-1]);
}
for(int j = m-2; j >= 0; j--){
a[i][j] = min(a[i][j], a[i][j+1] + WH[k][j]);
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
a[i][j] += WV[k][j];
// cout << i << " " << j << " " << a[i][j] << endl;
}
}
}
}
}st[1005];
const int BLSZ = 32;
void build(int l = 0, int r = n - 1, int id = 1){
if(r - l + 1 <= BLSZ)st[id] = matrix(l, r);
else {
int mid = (l+r)>>1;
build(l, mid, id<<1);
build(mid+1, r, id<<1|1);
st[id] = st[id<<1]*st[id<<1|1];
}
}
void edit(int k, int l = 0, int r = n-1, int id = 1){
if(r - l + 1 <= BLSZ)st[id] = matrix(l, r);
else {
int mid = (l+r)>>1;
if(k <= mid)edit(k, l, mid, id<<1);
else edit(k, mid+1, r, id<<1|1);
st[id] = st[id<<1]*st[id<<1|1];
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R, m = C;
for(int i = 0; i < n; i++){
for(int j = 0; j < m-1; j++)WH[i][j] = H[i][j];
}
for(int i = 0; i < n-1; i++){
for(int j = 0; j < m; j++)WV[i][j] = V[i][j];
}
build();
}
void changeH(int P, int Q, int W) {
WH[P][Q] = W;
edit(P);
}
void changeV(int P, int Q, int W) {
WV[P][Q] = W;
edit(P);
}
int escape(int V1, int V2) {
return st[1].a[V1][V2];
}
