// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "wombats.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5010, maxm = 210, SQ = 20, MAX = 4 * (maxn / SQ +1) , mod = 1e9 + 7, inf = 1e9 + 10;
int n, m;
int tmp[maxm][maxm], opt[maxm][maxm];
void knuth(int a[maxm][maxm], int b[maxm][maxm], int ans[maxm][maxm]){
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++)
tmp[i][j] = inf;
}
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
int x = a[i][j] + b[j][i];
if(x < tmp[i][i])
opt[i][i] = j, tmp[i][i] = x;
}
}
for(int ln = 1; ln < m; ln++){
for(int i = 0; i+ln < m; i++){
int j = i + ln;
for(int k = opt[i][j-1]; k <= opt[i+1][j]; k++){
int x = a[i][k] + b[k][j];
if(x < tmp[i][j])
opt[i][j] = k, tmp[i][j] = x;
}
}
}
for(int ln = 1; ln < m; ln++){
for(int i = ln; i < m; i++){
int j = i - ln;
for(int k = opt[i-1][j]; k <= opt[i][j+1]; k++){
int x = a[i][k] + b[k][j];
if(x < tmp[i][j])
opt[i][j] = k, tmp[i][j] = x;
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++)
ans[i][j] = tmp[i][j];
}
}
int cx[maxn][maxm], cy[maxn][maxm];
int ds[MAX][maxm][maxm];
int tmp2[maxm][maxm];
void restart(int l, int r, int ans[maxm][maxm]){
for(int a = 0; a < m; a++){
ans[a][a] = 0;
for(int b = a+1; b < m; b++)
ans[a][b] = ans[a][b-1] + cy[l][b-1];
for(int b = a-1; b >= 0; b--)
ans[a][b] = ans[a][b+1] + cy[l][b];
}
for(int w = l+1; w <= r; w++){
for(int a = 0; a < m; a++){
tmp2[a][a] = cx[w-1][a];
for(int b = a+1; b < m; b++)
tmp2[a][b] = tmp2[a][b-1] + cy[w][b-1];
for(int b = a-1; b >= 0; b--)
tmp2[a][b] = tmp2[a][b+1] + cy[w][b];
}
knuth(ans, tmp2, ans);
}
}
void build(int l = 0, int r = n, int id = 1){
assert(id < MAX);
if(r-l <= SQ){
restart(l, r, ds[id]);
return;
}
int mid = (l+r) >> 1;
build(l, mid, 2*id);
build(mid, r, 2*id+1);
knuth(ds[2*id], ds[2*id+1], ds[id]);
}
void change(int pos, int l = 0, int r = n, int id = 1){
if(r < pos || pos < l)
return;
if(r-l <= SQ){
restart(l, r, ds[id]);
return;
}
int mid = (l+r) >> 1;
change(pos, l, mid, 2*id);
change(pos, mid, r, 2*id+1);
knuth(ds[2*id], ds[2*id+1], ds[id]);
}
void init(int n, int m, int H[5000][200], int V[5000][200]){
--n;
::n = n, ::m = m;
for(int i = 0; i <= n; i++){
for(int j = 0; j < m; j++)
cy[i][j] = H[i][j], cx[i][j] = V[i][j];
}
build();
}
void changeH(int P, int Q, int W) {// Y
cy[P][Q] = W;
change(P);
}
void changeV(int P, int Q, int W){ // X
cx[P][Q] = W;
change(P);
}
int escape(int V1, int V2){
return ds[1][V1][V2];
}
