#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
int finans[205][205];
int sqrtans[100][205][205];
int sqrts[100], sqrte[100];
int h[5005][205], v[5005][205];
int n, m,di,ss;
int tempans[205][205] = { 0 };
int opt[205][205] = { 0 };
int curco[205][205] = { 0 };
void sqrtcal(int n)
{
memset(sqrtans[n], 10, sizeof(sqrtans[n]));
int i;
for (i = 0; i < m; i++)
sqrtans[n][i][i] = 0;
for (i = sqrts[n]; i <= sqrte[n]; i++)
{
memset(tempans, 10, sizeof(tempans));
int j,k;
int currdi = 0;
for (j = 0; j < m; j++)
{
int curdi = currdi;
for (k = 0; k < m; k++)
{
curco[j][k] = v[i][k] + curdi;
if (k < j)
{
curdi -= h[i][k];
}
else
{
curdi += h[i][k];
}
}
currdi += h[i][j];
}
for (j = 0; j < m; j++)
{
for (k = m - 1; k >= 0; k--)
{
int l;
for (l = (j ? opt[j - 1][k] : 0); l <= (k < m - 1 ? opt[j][k + 1] : m - 1); l++)
{
if (tempans[j][k] > sqrtans[n][j][l] + curco[l][k])
{
tempans[j][k] = sqrtans[n][j][l] + curco[l][k];
opt[j][k] = l;
}
}
}
}
for (j = 0; j < m; j++)
{
for (k = 0; k < m; k++)
{
sqrtans[n][j][k] = tempans[j][k];
}
}
}
}
void fincal()
{
memset(finans, 10, sizeof(finans));
int i;
for (i = 0; i < m; i++)
finans[i][i] = 0;
for (i =0; i <ss; i++)
{
memset(tempans, 10, sizeof(tempans));
int j, k;
for (j = 0; j < m; j++)
{
for (k = m - 1; k >= 0; k--)
{
int l;
for (l = (j ? opt[j - 1][k] : 0); l <= (k < m - 1 ? opt[j][k + 1] : m - 1); l++)
{
if (tempans[j][k] > finans[j][l] + sqrtans[i][l][k])
{
tempans[j][k] = finans[j][l] + sqrtans[i][l][k];
opt[j][k] = l;
}
}
}
}
for (j = 0; j < m; j++)
{
for (k = 0; k < m; k++)
{
finans[j][k] = tempans[j][k];
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
n = R;
m = C;
di = 50;
int i;
for (i = 0; i * di < n; i++)
{
sqrts[i] = i * di;
sqrte[i] = min(i * di + di - 1, n - 1);
}
ss = i;
for (i = 0; i < n; i++)
{
int j;
for (j = 0; j < m; j++)
{
h[i][j] = H[i][j];
v[i][j] = V[i][j];
}
}
for (i = 0; i < ss; i++)
{
sqrtcal(i);
}
fincal();
}
void changeH(int P, int Q, int W)
{
h[P][Q] = W;
sqrtcal(P / di);
fincal();
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
sqrtcal(P / di);
fincal();
}
int escape(int V1, int V2) {
return finans[V1][V2];
}
