#include "wombats.h"
#include "iostream"
#include "algorithm"
#include "vector"
#include "set"
#include "map"
#include "cstring"
#include "string"
#include "vector"
#include "cassert"
#include "queue"
#include "cstdio"
#include "cstdlib"
#include "ctime"
#include "cmath"
#include "bitset"
#include "numeric"
#include "iomanip"
using namespace std;
typedef long long ll;
typedef pair < int, int > ii;
const int N = 5000 + 5;
const int M = 200 + 5;
int n, m;
int a[N][M], b[N][M];
int t[1024][M][M];
void row(int i, int dp[N]) {
for(int j = m - 1; j >= 1; j--)
dp[j] = min(dp[j], dp[j + 1] + a[i][j]);
for(int j = 2; j <= m; j++)
dp[j] = min(dp[j], dp[j - 1] + a[i][j - 1]);
}
void calcDp(int x, int l, int r) {
for(int st = 1; st <= m; st++) {
for(int i = 1; i <= m; i++)
t[x][st][i] = 1e9 * (st != i);
row(l, t[x][st]);
for(int i = l; i < r; i++) {
for(int nd = 1; nd <= m; nd++)
t[x][st][nd] += b[i][nd];
row(i + 1, t[x][st]);
}
}
}
int opt[M][M];
void solve(int x, int x1, int x2, int i, int l, int r, int optL, int optR, int b[M]) {
if(l > r)
return;
int m = (l + r) >> 1;
int opt = -1;
t[x][i][m] = 1e9;
for(int j = optL; j <= optR; j++) {
int cost = t[x1][i][j] + b[j] + t[x2][j][m];
if(cost < t[x][i][m]) {
t[x][i][m] = cost;
opt = j;
}
}
solve(x, x1, x2, i, l, m - 1, optL, opt, b);
solve(x, x1, x2, i, m + 1, r, opt, optR, b);
}
void calc(int x, int x1, int x2, int b[M]) {
for(int i = 1; i <= m; i++)
solve(x, x1, x2, i, 1, m, 1, m, b);
}
void init(int x, int l, int r) {
if(r - l < 15) {
calcDp(x, l, r);
return;
}
int m = (l + r) >> 1;
init(x + x, l, m);
init(x + x + 1, m + 1, r);
calc(x, x + x, x + x + 1, b[m]);
}
void update(int x, int l, int r, int v) {
if(r - l < 15) {
calcDp(x, l, r);
return;
}
int m = (l + r) >> 1;
if(v <= m)
update(x + x, l, m, v);
else
update(x + x + 1, m + 1, r, v);
calc(x, x + x, x + x + 1, b[m]);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R;
m = C;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] = H[i - 1][j - 1], b[i][j] = V[i - 1][j - 1];
init(1, 1, n);
}
void changeH(int x, int y, int v) {
++x;
++y;
a[x][y] = v;
update(1, 1, n, x);
}
void changeV(int x, int y, int v) {
++x;
++y;
b[x][y] = v;
update(1, 1, n, x);
}
int escape(int x, int y) {
++x;
++y;
return t[1][x][y];
}
