#include"wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define ms(x, a) memset(x, a, sizeof x)
typedef long long ll;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f;
const int MR = 5000, MC = 200, BSZ = 70;
int R, C, H[MR][MC], V[MR][MC];
int N, blk[MR], blkL[MR], blkR[MR];
struct Item{
int d[MC][MC];
Item(){ ms(d, 0); }
int& operator()(int a, int b){ return d[a][b]; }
void setid(){ ms(d, 0x3f); for (int i = 0; i < C; ++i) d[i][i] = 0; }
void set(int r){
Item rhs;
for (int i = 0; i < C; ++i){
d[i][i] = V[r][i];
rhs(i, i) = 0;
for (int j = i - 1; j >= 0; --j){
d[i][j] = d[i][j + 1] - V[r][j + 1] + H[r][j] + V[r][j];
rhs(i, j) = rhs(i, j + 1) + H[r + 1][j];
}
for (int j = i + 1; j < C; ++j){
d[i][j] = d[i][j - 1] - V[r][j - 1] + H[r][j - 1] + V[r][j];
rhs(i, j) = rhs(i, j - 1) + H[r + 1][j - 1];
}
}
merge(rhs);
}
void merge(Item &rhs){
Item lhs = *this;
memcpy(lhs.d, d, MC * MC * sizeof(int));
// lhs.print();
// rhs.print();
ms(d, 0);
for (int i = 0; i < C; ++i){
for (int k = 0; k < C; ++k){
if (lhs(i, k) + rhs(k, i) < lhs(i, d[i][i]) + rhs(d[i][i], i)) d[i][i] = k;
}
}
for (int sz = 2; sz <= C; ++sz){
for (int l = 0, r = sz - 1; r < C; ++l, ++r){
for (int k = d[l][r - 1]; k <= d[l + 1][r]; ++k){
if (lhs(l, k) + rhs(k, r) < lhs(l, d[l][r]) + rhs(d[l][r], r)) d[l][r] = k;
}
}
for (int l = sz - 1, r = 0; l < C; ++l, ++r){
for (int k = d[l - 1][r]; k <= d[l][r + 1]; ++k){
if (lhs(l, k) + rhs(k, r) < lhs(l, d[l][r]) + rhs(d[l][r], r)) d[l][r] = k;
}
}
}
// print();
// cout << '\n' << '\n' << '\n';
for (int i = 0; i < C; ++i){
for (int j = 0; j < C; ++j){
d[i][j] = lhs(i, d[i][j]) + rhs(d[i][j], j);
}
}
// for (int j = C - 1; j >= 0; --j){
// d[i][j] = inf;
// for (int k = 0; k < C; ++k){
// d[i][j] = min(d[i][j], lhs(i, k) + rhs(k, j));
// }
// }
}
void print(){
cout << "~~~~~~~~~" << '\n';
for (int i = 0; i < C; ++i){
for (int j = 0; j < C; ++j){
cout << d[i][j] << " ";
}
cout << '\n';
}
cout << "~~~~~~~~~" << '\n';
}
} arr[MR / BSZ + 1], cur, ans;
void fix_block(int b){
// cout << "fixing : " << b << '\n';
arr[b].set(blkL[b]);
for (int i = blkL[b] + 1; i <= blkR[b]; ++i){
cur.set(i);
arr[b].merge(cur);
}
}
void fix_all(){
memcpy(ans.d, arr[0].d, MC * MC * sizeof(int));
for (int i = 1; i < N; ++i){
ans.merge(arr[i]);
}
}
void init(int r, int c, int h[5000][200], int v[5000][200]){
R = r, C = c;
memcpy(H, h, MR * MC * sizeof(int));
memcpy(V, v, MR * MC * sizeof(int));
ms(blkL, 0x3f);
for (int i = 0; i < R - 1; ++i){
int b = i / BSZ;
blk[i] = b;
blkL[b] = min(blkL[b], i);
blkR[b] = max(blkR[b], i);
}
N = (R - 2) / BSZ + 1;
for (int i = 0; i < N; ++i) fix_block(i);
fix_all();
}
void changeH(int p, int q, int w){
H[p][q] = w;
fix_block(blk[p]);
if (p != 0 && blk[p] != blk[p - 1]){
fix_block(blk[p - 1]);
}
fix_all();
}
void changeV(int p, int q, int w){
V[p][q] = w;
fix_block(blk[p]);
fix_all();
}
int escape(int v1, int v2){
return ans(v1, v2);
}
