#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#include "wombats.h"
const int INF = 1e9;
const int Bcnt = 21;
const int B = (5000 + Bcnt - 1) / Bcnt;
int R, C;
int H[5000][200];
int V[5000][200];
int mem[Bcnt][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);
}
int sav[200];
int snum = 1;
void changeH(int P, int Q, int W)
{
snum++;
H[P][Q] = W;
upd(P / B);
}
void changeV(int P, int Q, int W)
{
snum++;
V[P][Q] = W;
upd(P / B);
}
int dp2[Bcnt][200];
int fb;
void f(int l, int r, int s, int g)
{
if(r <= l)
{
if(l == r)
{
int v = INF;
for(int i = s; i <= g; i++)
v = min(v, dp2[fb - 1][i] + mem[fb][i][l]);
dp2[fb][l] = v;
}
return;
}
int x = (l + r) / 2, v = INF, p;
for(int i = s; i <= g; i++)
{
int t = dp2[fb - 1][i] + mem[fb][i][x];
if(t < v)
{
v = t;
p = i;
}
}
dp2[fb][x] = v;
f(l, x - 1, s, p);
f(x + 1, r, p, g);
}
int ans[200][200];
int escape(int V1, int V2)
{
if(sav[V1] != snum)
{
sav[V1] = snum;
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);
}
for(int i = 0; i < C; i++)
ans[V1][i] = dp2[(R - 1) / B][i];
}
return ans[V1][V2];
}
