#include <bits/stdc++.h>
using namespace std;
#include "wombats.h"
const int INF = 1e9;
const int B = 250;
int R, C;
int H[5001][200];
int V[5001][200];
int mem[5000 / B + 1][200][200];
int dp1[200];
void upd(int b)
{
int s = b * B;
int l = min(B, R - s);
for(int i = 0; i < C; i++)
{
for(int j = 0; j < C; j++)
dp1[j] = INF;
dp1[i] = 0;
for(int j = 0; j < l; j++)
{
for(int k = 1; k < C; k++)
dp1[k] = min(dp1[k], dp1[k - 1] + H[j + s][k - 1]);
for(int k = C - 2; k >= 0; k--)
dp1[k] = min(dp1[k], dp1[k + 1] + H[j + s][k]);
for(int k = 0; k < C; k++)
dp1[k] += V[j + s][k];
}
for(int j = 0; j < C; j++)
mem[b][i][j] = dp1[j];
}
}
void init(int _R, int _C, int _H[5000][200], int _V[5000][200])
{
R = _R;
C = _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 < (R + B - 1) / B; i++)
upd(i);
}
void changeH(int P, int Q, int W)
{
H[P][Q] = W;
upd(P / B);
}
void changeV(int P, int Q, int W)
{
V[P][Q] = W;
upd(P / B);
}
int dp2[5000 / B + 1][200];
int fb;
void f(int l, int r, int s, int g)
{
if(r < l)
return;
int x = (l + r) / 2, p = s;
dp2[fb][x] = INF;
for(int i = s; i <= g; i++)
{
int t = dp2[fb - 1][i] + mem[fb][i][x];
if(t < dp2[fb][x])
{
dp2[fb][x] = t;
p = i;
}
}
f(l, x - 1, s, p);
f(x + 1, r, p, g);
}
int escape(int V1, int V2)
{
for(int i = 0; i < C; i++)
dp2[0][i] = mem[0][V1][i];
for(int i = 1; i < (R + B - 1) / B; i++)
{
fb = i;
f(0, C - 1, 0, C - 1);
}
return dp2[(R - 1) / B][V2];
}
