#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], dp[200][200], o[201];
void update(int pos, int id = 1, int l = 0, int r = (m - 1) / 10){
if (pos < l || r < pos)
return;
if (l == r){
memset(dp, 0x3f, sizeof(dp));
for(int i = 0; i < n; i++)
dp[i][i] = 0;
for(int r = pos * BLOCK_SIZE; r < min((pos + 1) * BLOCK_SIZE, m); r++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n - 1; j++)
dp[i][j] = min(dp[i][j], dp[i][j + 1] + h[r][j]);
for(int j = 0; j < n - 1; j++)
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + h[r][j]);
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dp[i][j] += v[r][j];
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
d[id][i][j] = dp[i][j];
return;
}
int mid = (l + r) >> 1;
update(pos, id << 1, l, mid);
update(pos, id << 1 | 1, mid + 1, r);
memset(dp[id], 0x3f, sizeof(dp[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 = 0; k < n; 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];
}
}
void init(int r, int c, int _h[5000][200], int _v[5000][200]){
m = r;
n = c;
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 <= m / BLOCK_SIZE; 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];
}
