#include "wombats.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
const int MR = 5e3+10;
const int SM = 20;
const int MC = 2e2+10;
int R, C, B, H[5000][200], V[5000][200], st[1024][MC][MC], dp[MC], best[MC];
bool cur;
void compute_block(int n, int l, int r)
{
for(int i=0;i<C;++i)
{
memset(dp, 0x3f, C*sizeof*dp);
dp[i]=0;
for(int j=l;j<r;++j)
{
for(int c=0;c+1<C;++c)
ckmin(dp[c+1], dp[c]+H[j][c]);
for(int c=C-1;c>0;--c)
ckmin(dp[c-1], dp[c]+H[j][c-1]);
if(j+1<R)
for(int c=0;c<C;++c)
dp[c] += V[j][c];
}
memcpy(st[n][i], dp, C*sizeof*dp);
}
}
void merge(int x, int y, int z)
{
memset(st[z], 0x3f, sizeof st[z]);
memset(best, 0, C*sizeof*best);
best[C]=C-1;
/*
for(int i=0;i<C;++i) for(int j=0;j<C;++j) for(int k=0;k<C;++k)
ckmin(st[z][i][j], st[x][i][k]+st[y][k][j]);
*/
for(int d=-C+1;d<C;++d)
for(int i=std::max(0, -d), mi=(C-std::max(0, d));i<mi;++i)
{
int j=i+d;
int tr=-1;
for(int k=best[i];k<=best[i+1];++k)
if(ckmin(st[z][i][j], st[x][i][k]+st[y][k][j]))
tr=k;
best[i]=tr;
}
}
void upd(int n, int l, int r, int q)
{
if(r-l<=SM)
compute_block(n, l, r);
else
{
int m=l+(r-l)/2;
if(q==-1 || q<m) upd(n<<1, l, m, q);
if(q==-1 || m<=q) upd(n<<1|1, m, r, q);
merge(n<<1, n<<1|1, n);
}
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
::R=R;
::C=C;
memcpy(::H, H, sizeof ::H);
memcpy(::V, V, sizeof ::V);
upd(1, 0, R, -1);
}
void changeH(int P, int Q, int W) { // 500x tot
H[P][Q]=W;
upd(1, 0, R, P);
}
void changeV(int P, int Q, int W) { // 500x tot
V[P][Q]=W;
upd(1, 0, R, P);
}
int escape(int V1, int V2) { // 200000x
//return mat[0][V1][V2];
return st[1][V1][V2];
}
