#include "wombats.h"
#define group_size 10
const int NON = 0x0fffffff;
const int Z = 512;
int N, M, G, Start[Z], End[Z], MADE;
int ANS[200][200],GO[Z*2][200][200],NOW[200];
int H[5001][200],V[5001][200];
inline int min(int a, int b){return a < b ? a : b;}
void merge(int x)
{
int i,j,k,s,p;
NOW[0] = 0; NOW[1] = M-1;
for (i=M-1;i>=0;i--){
for (j=M-1;j>=i;j--){
s = NON; p = NOW[j-i];
for (k=NOW[j-i];k<=NOW[j-i+1];k++){
int &a = GO[x*2][j-i][k];
int &b = GO[x*2+1][k][j];
if (s >= a + b){
s = a + b;
p = k;
}
}
GO[x][j-i][j] = s;
NOW[j-i+1] = p;
}
NOW[M-i+1] = M-1;
}
NOW[0] = 0; NOW[1] = M-1;
for (i=M-1;i>=0;i--){
for (j=M-1;j>=i;j--){
s = NON; p = NOW[j-i];
for (k=NOW[j-i];k<=NOW[j-i+1];k++){
int &a = GO[x*2][j][k];
int &b = GO[x*2+1][k][j-i];
if (s >= a + b){
s = a + b;
p = k;
}
}
GO[x][j][j-i] = s;
NOW[j-i+1] = p;
}
NOW[M-i+1] = M-1;
}
}
void modify(int g)
{
int i,j,k,x=g+Z;
if (g >= G){
for (i=0;i<M;i++){
for (j=0;j<M;j++){
GO[x][i][j] = i == j ? 0 : NON;
}
}
}
else{
for (i=0;i<M;i++){
for (j=0;j<M;j++) NOW[j] = NON;
NOW[i] = 0;
for (k=Start[g];k<=End[g];k++){
for (j=1;j<M;j++) NOW[j] = min(NOW[j],NOW[j-1]+H[k][j-1]);
for (j=M-2;j>=0;j--) NOW[j] = min(NOW[j],NOW[j+1]+H[k][j]);
for (j=0;j<M;j++) NOW[j] += V[k][j];
}
for (j=0;j<M;j++) GO[x][i][j] = NOW[j];
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
N = R; M = C;
G = (R + group_size - 1) / group_size;
int i,j,c;
for (i=c=0;i<G;i++){
Start[i] = c;
c += group_size;
End[i] = c - 1;
}
if (End[G-1] >= R) End[G-1] = R - 1;
if (Start[G-1] > End[G-1]) G--;
for (i=0;i<R;i++) for (j=0;j<C-1;j++) ::H[i][j] = H[i][j];
for (i=0;i<R-1;i++) for (j=0;j<C;j++) ::V[i][j] = V[i][j];
for (i=0;i<Z;i++) modify(i);
for (i=Z-1;i>=1;i--) merge(i);
}
void change(int g)
{
modify(g);
int x = (g + Z) >> 1;
while (x){
merge(x);
x >>= 1;
}
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
change(P/group_size);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
change(P/group_size);
}
int escape(int V1, int V2) {
return GO[1][V1][V2];
}
