#include "wombats.h"
int n, m;
int ph[5130][210];
int pv[5130][210];
const int itsz = 512;
int tarr[210];
struct stnode {
int arr[210][210];
stnode operator+(const stnode& r)const {
stnode res;
for (int i = 0; i < m; i++) {
tarr[i] = m - 1;
}
for (int i = m - 1; i >= 0; i--) {
int larr = 0;
for (int j = 0; j < m; j++) {
int carr = -1;
int cres = 2.14e9;
for (int k = larr; k <= tarr[j]; k++) {
int sres = arr[i][k] + r.arr[k][j];
if (cres > sres) {
cres = sres;
carr = k;
}
}
res.arr[i][j] = cres;
tarr[j] = carr;
larr=carr;
}
}
return res;
}
};
stnode st[1030];
int dp[210][210];
void buildnode(int x) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = 2.14e9;
}
dp[i][i] = 0;
}
for (int lv = x * 10; lv < x * 10 + 10; lv++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < m - 1; j++) {
if (dp[i][j + 1] > dp[i][j] + ph[lv][j])dp[i][j + 1] = dp[i][j] + ph[lv][j];
}
for (int j = m - 2; j >= 0; j--) {
if (dp[i][j] > dp[i][j + 1] + ph[lv][j])dp[i][j] = dp[i][j + 1] + ph[lv][j];
}
for (int j = 0; j < m; j++) {
dp[i][j] += pv[lv][j];
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
st[x + itsz].arr[i][j] = dp[i][j];
}
}
}
void refreshnode(int x) {
buildnode(x);
x += itsz;
x /= 2;
while (x >= 1) {
st[x] = st[x * 2] + st[x * 2 + 1];
x /= 2;
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R;
m = C;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
ph[i][j] = H[i][j];
}
}
for (int i = n; i <= 5120; i++) {
for (int j = 0; j < m - 1; j++) {
ph[i][j] = 5.3e6;
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
pv[i][j] = V[i][j];
}
}
for (int i = n - 1; i <= 5120; i++) {
for (int j = 0; j < m; j++) {
pv[i][j] = 0;
}
}
for (int i = 0; i < itsz; i++) {
buildnode(i);
}
for (int i = itsz - 1; i >= 1; i--) {
st[i] = st[i * 2] + st[i * 2 + 1];
}
}
void changeH(int P, int Q, int W) {
ph[P][Q] = W;
refreshnode(P / 10);
}
void changeV(int P, int Q, int W) {
pv[P][Q] = W;
refreshnode(P / 10);
}
int escape(int V1, int V2) {
return st[1].arr[V1][V2];
}
