#include "wombats.h"
#include "bits/stdc++.h"
using namespace std;
#define left lft
#define right ryt
#define div damn
int t[505 * 2][205][205];
int R, C;
int H[5005][205];
int V[5005][205];
int dp[105][205][205];
const int inf = 1e9;
const int leaf = 10;
int start, div, node, left, right;
void solver(int b, int e, int from, int to) {
if(b > e) return ;
int mid = (b + e) >> 1;
int opt = -1;
int cost = inf;
for(int i = from; i <= to; i++) {
int sum = t[left][start][i] + V[div][i] + t[right][i][mid];
if(sum < cost) {
cost = sum;
opt = i;
}
}
t[node][start][mid] = cost;
solver(b, mid - 1, from, opt);
solver(mid + 1, e, opt, to);
}
void transition(int c, int b, int e) {
left = c << 1;
right = left + 1;
div = (b + e) >> 1;
node = c;
for(int i = 0; i < C; i++) {
start = i;
solver(0, C - 1, 0, C - 1);
}
}
void solve(int c, int b, int e) {
for(int x = 0; x < C; x++) {
for(int j = 0; j < C; j++) {
dp[0][x][j] = 0;
for(int k = min(x, j); k < max(x, j); k++) {
dp[0][x][j] += H[b][k];
}
}
}
for(int i = b + 1; i <= e; i++) {
for(int x = 0; x < C; x++) {
for(int j = 0; j < C; j++) {
dp[i - b][x][j] = inf;
}
int sum = 0;
int opt = inf;
for(int j = 0; j < C; j++) {
opt = min(opt, -sum + dp[i - b - 1][x][j] + V[i - 1][j]);
dp[i - b][x][j] = min(dp[i - b][x][j], opt + sum);
sum += H[i][j];
}
sum = 0;
opt = inf;
for(int j = C - 1; j >= 0; j--) {
sum += H[i][j];
opt = min(opt, -sum + dp[i - b - 1][x][j] + V[i - 1][j]);
dp[i - b][x][j] = min(dp[i - b][x][j], opt + sum);
}
}
}
for(int i = 0; i < C; i++) {
for(int j = 0; j < C; j++) {
t[c][i][j] = dp[e - b][i][j];
}
}
}
void build(int c = 1, int b = 0, int e = R - 1) {
if(b == e || ((c << 1) + 1) >= 1000) {
solve(c, b, e);
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
build(l, b, m);
build(r, m+1, e);
transition(c, b, e);
}
void update(int x, int c = 1, int b = 0, int e = R - 1) {
if(b == e || ((c << 1) + 1) >= 1000) {
solve(c, b, e);
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) update(x, l, b, m);
else update(x, r, m+1, e);
transition(c, b, e);
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
R = r; C = c;
for(int i = 0; i < R; i++) {
for(int j = 0; j < C - 1; j++) {
H[i][j] = h[i][j];
}
}
for(int i = 0; i < R - 1; i++) {
for(int j = 0; j < C; j++) {
V[i][j] = v[i][j];
}
}
build();
}
void changeH(int x, int y, int p) {
H[x][y] = p;
update(x);
}
void changeV(int x, int y, int p) {
V[x][y] = p;
update(x + 1);
}
int escape(int x, int y) {
return t[1][x][y];
}
