#include <bits/stdc++.h>
#include "wombats.h"
#define int int64_t
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cout << (#x) << ": " << (x) <<"\n"
#else
#define debug(x)
#endif
constexpr static int MXR = 5000;
constexpr static int MXSQR = 80;
constexpr static int MXC = 200;
constexpr static int INF = 1e18;
int r, c, sqr, sqr_size;
int ways[MXSQR][MXC][MXC];
int complete_ways[MXC][MXC];
int min_dist[MXR][MXC];
int h[MXR][MXC];
int v[MXR][MXC];
int tmp[MXC][MXC];
bitset<MXC> visited[MXR];
int add(int a, int b)
{
if (INF - a < b) return INF;
return a + b;
}
void merge_sections()
{
for (int i = 0; i < c; i++)
for (int j = 0; j < c; j++)
complete_ways[i][j] = (i==j) ? 0 : INF;
for (int i = 0; i < sqr; i++) // C^3 :(
{
for (int j = 0; j < c; j++)
for (int k = 0; k < c; k++)
tmp[j][k] = INF;
for (int j = 0; j < c; j++)
for (int k = 0; k < c; k++)
for (int l = 0; l < c; l++)
tmp[j][k] = min(tmp[j][k], add(complete_ways[j][l], ways[i][l][k]));
for (int j = 0; j < c; j++)
for (int k = 0; k < c; k++)
complete_ways[j][k] = tmp[j][k];
}
}
void calculate_section(int x)
{
int ss = x*sqr_size, ee = min((x+1)*sqr_size, r-1);
for (int root = 0; root < c; root++)
{
for (int k = ss; k <= ee; k++)
{
for (int l = 0; l < c; l++)
{
min_dist[k][l] = INF;
visited[k][l] = false;
}
}
priority_queue<array<int, 3>> pq;
min_dist[ss][root] = 0;
pq.push({0, ss, root});
while (pq.size())
{
auto [_, i, j] = pq.top();
pq.pop();
if (visited[i][j])
continue;
visited[i][j] = true;
if (i == ee)
ways[x][root][j] = min_dist[i][j];
if (j > 0 && min_dist[i][j] + h[i][j-1] < min_dist[i][j-1])
{
min_dist[i][j-1] = min_dist[i][j] + h[i][j-1];
pq.push({-min_dist[i][j-1], i, j-1});
}
if (j < c-1 && min_dist[i][j] + h[i][j] < min_dist[i][j+1])
{
min_dist[i][j+1] = min_dist[i][j] + h[i][j];
pq.push({-min_dist[i][j+1], i, j+1});
}
if (i < ee && min_dist[i][j] + v[i][j] < min_dist[i+1][j])
{
min_dist[i+1][j] = min_dist[i][j] + v[i][j];
pq.push({-min_dist[i+1][j], i+1, j});
}
}
}
}
void init(int32_t R, int32_t C, int32_t H[5000][200], int32_t V[5000][200])
{
r = R;
c = C;
sqr_size = (int)sqrt((double)R*C);
sqr = R / sqr_size;
if (R % sqr_size)
sqr++;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
h[i][j] = H[i][j];
v[i][j] = V[i][j];
}
}
for (int i = 0; i < sqr; i++)
calculate_section(i);
merge_sections();
}
void changeH(int32_t p, int32_t q, int32_t w)
{
h[p][q] = w;
calculate_section(p/sqr_size);
if (!(p%sqr_size) && p != 0)
calculate_section((p/sqr_size)-1);
merge_sections();
}
void changeV(int32_t p, int32_t q, int32_t w)
{
v[p][q] = w;
calculate_section(p/sqr_size);
merge_sections();
}
int32_t escape(int32_t V1, int32_t V2)
{
return complete_ways[V1][V2];
}
