#include "wombats.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
#define LoopR(x, l, r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
const int R = 5000;
const int S = 500;
int r;
const int C = 200;
const int Q = 500;
const int vs = 8;
typedef int vec __attribute__((vector_size(4*vs), aligned(4*vs)));
vec H[R][C/vs], V[R][C];
vec PS[R][C/vs];
vec ans[C][C/vs];
vec pans[R/S][C][C/vs];
#define MIN(x, y) ((x)<(y)?(x):(y))
int i2v(int x) { return x % (C/vs) * vs + x / (C/vs); }
void to_right(vec *ans, int p)
{
Loop (i,0,C/vs-1)
ans[i+1] = MIN(ans[i+1], ans[i] + H[p][i]);
int mn = 1e9;
vec x;
x[0] = mn;
Loop (i,0,vs-1) {
mn = MIN(mn, ans[C/vs-1][i] - PS[p][C/vs-1][i]);
x[i+1] = mn;
}
Loop (i,0,C/vs)
ans[i] = MIN(ans[i], x + PS[p][i]);
}
void to_left(vec *ans, int p)
{
LoopR (i,0,C/vs-1)
ans[i] = MIN(ans[i], ans[i+1] + H[p][i]);
int mn = 1e9;
vec x;
x[vs-1] = mn;
LoopR (i,0,vs-1) {
mn = MIN(mn, ans[0][i+1] + PS[p][0][i+1]);
x[i] = mn;
}
LoopR (i,0,C/vs)
ans[i] = MIN(ans[i], x - PS[p][i]);
}
void down(vec *ans, int p)
{
Loop (i,0,C/vs)
ans[i] += V[p][i];
}
void recalcp(int s)
{
int sl = s*S, sr = min(s*S+S, r);
Loop (i,0,C) {
Loop (x,0,C/vs) Loop (y,0,vs)
pans[s][i2v(i)][x][y] = 1e6;
pans[s][i2v(i)][i % (C/vs)][i / (C/vs)] = 0;
}
Loop (i,sl,sr) {
Loop (p,0,C) {
to_right(pans[s][p], i);
to_left(pans[s][p], i);
}
if (i < r-1) {
Loop (p,0,C)
down(pans[s][p], i);
}
}
}
void recalc()
{
memcpy(ans, pans[0], sizeof(ans));
static int tmp[C][C];
int (*a)[C] = (int (*)[C])(void *)ans;
for (int s = 1; s*S < r; ++s) {
int (*b)[C] = (int (*)[C])(void *)pans[s];
Loop (i,0,C) Loop (j,0,C)
tmp[i][j] = a[i][0] + b[0][j];
Loop (i,0,C) Loop (j,1,C) Loop (k,0,C)
tmp[i][k] = MIN(tmp[i][k], a[i][j] + b[j][k]);
memcpy(ans, tmp, sizeof(ans));
}
}
void recalc_ps(int p)
{
Loop (i,0,vs)
PS[p][0][i] = 0;
Loop (i,0,C/vs-1)
PS[p][i+1] = PS[p][i] + H[p][i];
vec x = {};
Loop (i,0,vs-1)
x[i+1] = x[i] + PS[p][C/vs-1][i] + H[p][C/vs-1][i];
Loop (i,0,C/vs)
PS[p][i] += x;
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
::r = r;
Loop (i,0,r) Loop (j,0,C-1) {
int x = j < c-1? h[i][j]: 1001;
H[i][j % (C/vs)][j / (C/vs)] = x;
}
Loop (i,0,r-1) Loop (j,0,C) {
int x = j < c? v[i][j]: 1001;
V[i][j % (C/vs)][j / (C/vs)] = x;
}
Loop (i,0,r)
recalc_ps(i);
for (int i = 0; i*S < r; ++i)
recalcp(i);
recalc();
}
void changeH(int P, int Q, int W) {
H[P][Q % (C/vs)][Q / (C/vs)] = W;
recalc_ps(P);
recalcp(P/S);
recalc();
}
void changeV(int P, int Q, int W) {
V[P][Q % (C/vs)][Q / (C/vs)] = W;
recalcp(P/S);
recalc();
}
int escape(int V1, int V2) {
return ans[i2v(V1)][V2 % (C/vs)][V2 / (C/vs)];
}
