#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int T = 230;
int R, C, H[5000][200], V[5000][200];
int bl[30][200][200], dp[2][200][200];
void calc(int l, int r, int lo, int hi, int block, int V1){
if (l >= r)
return;
int m = (l+r) >> 1, opt = -1;
dp[1][V1][m] = inf;
for (int i = lo; i < hi; i++){
if (dp[0][V1][i] + bl[block][i][m] < dp[1][V1][m]){
opt = i;
dp[1][V1][m] = dp[0][V1][i] + bl[block][i][m];
}
}
calc(l, m, lo, opt+1, block, V1);
calc(m+1, r, opt, hi, block, V1);
}
void MakeAll(){
for (int V1 = 0; V1 < C; V1++){
for (int i = 0; i < C; i++)
dp[0][V1][i] = bl[0][V1][i];
for (int i = T; i < R; i += T){
int block = i/T;
calc(0, C, 0, C, block, V1);
for (int j = 0; j < C; j++)
dp[0][V1][j] = dp[1][V1][j];
}
}
}
void ChangeBlock(int block){
for (int j = 0; j < C; j++){
for (int k = 0; k < C; k++)
bl[block][j][k] = inf;
bl[block][j][j] = 0;
for (int k = j+1; k < C; k++)
bl[block][j][k] = bl[block][j][k-1] + H[T*block][k-1];
for (int k = j-1; k >= 0; k--)
bl[block][j][k] = bl[block][j][k+1] + H[T*block][k];
for (int k = 0; k < C; k++)
bl[block][j][k] += V[T*block][k];
for (int i = T*block+1; i < min(R, T*(block+1)); i++){
for (int k = 1; k < C; k++)
bl[block][j][k] = min(bl[block][j][k], bl[block][j][k-1] + H[i][k-1]);
for (int k = C-2; k >= 0; k--)
bl[block][j][k] = min(bl[block][j][k], bl[block][j][k+1] + H[i][k]);
for (int k = 0; k < C; k++)
bl[block][j][k] += V[i][k];
}
}
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
R = r, C = c;
for (int i = 0; i < 5000; i++)
for (int j = 0; j < 200; j++)
H[i][j] = h[i][j], V[i][j] = v[i][j];
for (int i = 0; i < R; i += T)
ChangeBlock(i/T);
MakeAll();
return;
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
ChangeBlock(P/T);
MakeAll();
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
ChangeBlock(P/T);
MakeAll();
}
int escape(int V1, int V2) {
return dp[0][V1][V2];
}
