#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
const int BLOCK_SIZE = 10;
int n, m, h[5000][200], v[5000][200], d[1024][200][200], o[201];
void update(int pos, int id = 1, int l = 0, int r = 499){
if (pos < l || r < pos)
return;
if (l == r){
memset(d[id], 0x3f, sizeof(d[id]));
for(int i = 0; i < n; i++)
d[id][i][i] = 0;
for(int k = pos * BLOCK_SIZE; k < (pos + 1) * BLOCK_SIZE; k++)
for(int i = 0; i < n; i++){
for(int j = n - 2; j >= 0; j--)
d[id][i][j] = min(d[id][i][j], d[id][i][j + 1] + h[k][j]);
for(int j = 1; j < n; j++)
d[id][i][j] = min(d[id][i][j], d[id][i][j - 1] + h[k][j - 1]);
for(int j = 0; j < n; j++)
d[id][i][j] += v[k][j];
}
return;
}
int mid = (l + r) >> 1;
update(pos, id << 1, l, mid);
update(pos, id << 1 | 1, mid + 1, r);
memset(d[id], 0x3f, sizeof(d[id]));
memset(o, 0, sizeof(o));
o[n] = n - 1;
for(int i = 0; i < n; i++)
for(int j = n - 1; j >= 0; j--)
for(int k = o[j]; k <= o[j + 1]; k++)
if (d[id][i][j] >= d[id << 1][i][k] + d[id << 1 | 1][k][j]){
d[id][i][j] = d[id << 1][i][k] + d[id << 1 | 1][k][j];
o[j] = k;
}
}
void init(int r, int c, int _h[5000][200], int _v[5000][200]){
m = r;
n = c;
memset(h, 0x3f, sizeof(h));
for(int i = 0; i < r; i++)
for(int j = 0; j < c - 1; j++)
h[i][j] = _h[i][j];
for(int i = 0; i < r - 1; i++)
for(int j = 0; j < c; j++)
v[i][j] = _v[i][j];
for(int i = 0; i <= 499; i++)
update(i);
}
void changeH(int p, int q, int w){
h[p][q] = w;
update(p / BLOCK_SIZE);
}
void changeV(int p, int q, int w){
v[p][q] = w;
update(p / BLOCK_SIZE);
}
int escape(int v1, int v2){
return d[1][v1][v2];
}
