#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000000;
int A[5000][200], B[5000][200];
int dp[10][200][200];
int cho[200][200];
int n, m;
int tmp[200][200];
void Merge(int f[200][200], int g[200][200], int wei[200], int h[200][200]) {
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
int r = i + 1 < m ? cho[i + 1][j] : m - 1, l = j ? cho[i][j - 1] : 0;
tmp[i][j] = INF;
for (int k = l; k <= r; k++) {
if (tmp[i][j] > f[i][k] + wei[k] + g[k][j]) {
tmp[i][j] = f[i][k] + wei[k] + g[k][j];
cho[i][j] = k;
}
}
}
}
for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) h[i][j] = tmp[i][j];
}
struct Segment_tree {
int T[1024][200][200];
void Calc(int now, int l, int r) {
int W = min(10, n - l * 10);
for (int i = 0; i < W; i++) {
for (int j = 0; j < m; j++) {
dp[i][j][j] = 0;
for (int k = j - 1; k >= 0; k--) dp[i][j][k] = dp[i][j][k + 1] + A[l * 10 + i][k];
for (int k = j + 1; k < m; k++) dp[i][j][k] = dp[i][j][k - 1] + A[l * 10 + i][k - 1];
}
}
for (int j = 0; j < m; j++) for (int k = 0; k < m; k++) T[now][j][k] = dp[0][j][k];
for (int i = 1; i < W; i++) Merge(T[now], dp[i], B[l * 10 + i - 1], T[now]);
}
void pushup(int now, int mid) {
Merge(T[now << 1], T[now << 1 | 1], B[mid * 10 + 9], T[now]);
}
void Build(int now, int l, int r) {
if (l == r) {
Calc(now, l, r);
return ;
}
int mid = l + r >> 1;
Build(now << 1, l, mid), Build(now << 1 | 1, mid + 1, r);
pushup(now, mid);
}
void Update(int now, int l, int r, int pos) {
if (l == r) {
Calc(now, l, r);
return ;
}
int mid = l + r >> 1;
if (pos <= mid) Update(now << 1, l, mid, pos);
else Update(now << 1 | 1, mid + 1, r, pos);
pushup(now, mid);
}
}seg;
void init(int N, int M, int h[5000][200], int v[5000][200]) {
n = N, m = M;
for (int i = 0; i < n; i++) for (int j = 0; j + 1 < m; j++) A[i][j] = h[i][j];
for (int i = 0; i + 1 < n; i++) for (int j = 0; j < m; j++) B[i][j] = v[i][j];
seg.Build(1, 0, (n - 1) / 10);
}
void changeH(int P, int Q, int W) {
A[P][Q] = W, seg.Update(1, 0, (n - 1) / 10, P / 10);
}
void changeV(int P, int Q, int W) {
B[P][Q] = W;
seg.Update(1, 0, (n - 1) / 10, P / 10);
if ((P + 1) / 10 != P / 10) seg.Update(1, 0, (n - 1) / 10, (P + 1) / 10);
}
int escape(int V1, int V2) {
return seg.T[1][V1][V2];
}
