#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int B = 500, Cmax = 205, Rmax = 5005;
const int inf = 1e8;
int N, M, rm;
int h[Rmax][Cmax], v[Rmax][Cmax];
static void min_to(int &x, int y) { if(x > y) x = y ;}
static void rec(int a[], int p)
{
int i;
for(i=1; i<M; ++i)
min_to(a[i], a[i-1] + h[p][i-1]);
for(i=M-2; i>=0; --i)
min_to(a[i], a[i+1] + h[p][i]);
}
struct matrix
{
int a[Cmax][Cmax];
void combine(matrix &A, matrix &B, int pos)
{
int i, j, k;
for(i=0; i<M; ++i)
for(j=0; j<M; ++j)
{
a[i][j] = inf;
for(k=0; k<M; ++k)
min_to(a[i][j], A.a[i][k] + B.a[k][j] + v[pos][k]);
}
}
void refresh(int bucket)
{
int i, j, k;
for(i=0; i<M; ++i)
{
for(j=0; j<M; ++j)
a[i][j] = (i==j ? 0 : inf);
for(k = bucket * B; k < (bucket+1) * B && k < N; ++k)
{
rec(a[i], k);
if(k + 1 < min(B * (bucket+1), N))
for(j=0; j<M; ++j)
a[i][j] += v[k][j];
}
}
}
};
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
namespace aint
{
matrix a[ (Rmax / B + 3) << 2];
void update(int node, int st, int dr, int pos)
{
if(st == dr)
{
a[node].refresh(st);
return;
}
if(pos <= mid) update(left_son, st, mid, pos);
else update(right_son, mid+1, dr, pos);
a[node].combine(a[left_son], a[right_son], (mid+1) * B - 1);
}
void build(int node, int st, int dr)
{
if(st == dr)
{
a[node].refresh(st);
return;
}
build(left_son, st, mid);
build(right_son, mid+1, dr);
a[node].combine(a[left_son], a[right_son], (mid+1) * B - 1);
}
int get_answer(int start, int finish)
{
return a[1].a[start][finish];
}
};
void init(int R, int C, int H[5000][200], int V[5000][200])
{
N = R; M = C;
rm = (N-1) / B;
int i, j;
for(i=0; i<N; ++i)
for(j=0; j<M; ++j)
h[i][j] = H[i][j], v[i][j] = V[i][j];
aint::build(1, 0, rm);
}
void changeH(int P, int Q, int W)
{
h[P][Q] = W;
aint::update(1, 0, rm, P / B);
}
void changeV(int P, int Q, int W)
{
v[P][Q] = W;
aint::update(1, 0, rm, P / B);
}
int escape(int V1, int V2)
{
return aint::get_answer(V1, V2);
}
