#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long double db;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7;
int R, C;
typedef array<array<int, 200>, 200> T;
void CLEAR(T& a){
for(int i = 0; i < C; i++){
for(int j = 0; j < C; j++){
a[i][j] = MOD;
}
}
}
void updMult(const T& a, const T& b, T& c, int k, pi irange = mp(0, C-1), pi jrange = mp(0, C-1)){
if(irange.f > irange.s) return;
int i_M = (irange.f+irange.s)/2;
int best_j = -1;
for(int j = jrange.f; j <= jrange.s; j++){
int val = a[i_M][j]+b[j][k];
if(val < c[i_M][k]){
best_j = j;
c[i_M][k] = val;
}
}
assert(best_j != -1);
updMult(a, b, c, k, mp(irange.f, i_M-1), mp(jrange.f, best_j));
updMult(a, b, c, k, mp(i_M+1, irange.s), mp(best_j, jrange.s));
}
// void mult(const T& a, const T& b, T& c){ // c = a*b, c should be a new variable
// CLEAR(c);
// for(int i = 0; i < C; i++){
// updMult(a, b, c, i);
// }
// #warning check whether mult is correct
// }
int optimal[205][205];
void mult(const T& a, const T& b, T& c){ // c = a*b, c should be a new variable
CLEAR(c);
auto updateTrans = [&](int i, int j, int k){
if(a[i][j]+b[j][k] < c[i][k]){
c[i][k] = a[i][j]+b[j][k];
optimal[i][k] = j;
}
};
for(int i = 0; i < C; i++){
for(int j = 0; j < C; j++){
updateTrans(i, j, i);
}
}
for(int dif = 1; dif < C; dif++){
for(int i = 0; i+dif < C; i++){
for(int j = optimal[i][i+dif-1]; j <= optimal[i+1][i+dif]; j++){
updateTrans(i, j, i+dif);
}
}
}
for(int dif = -1; dif >= -C; dif--){
for(int i = C-1; i+dif >= 0; i--){
for(int j = optimal[i-1][i+dif]; j <= optimal[i][i+dif+1]; j++){
updateTrans(i, j, i+dif);
}
}
}
}
int H[5005][205];
int Hsum[5005][205];
int V[5005][205];
const int SZ = 1030; //SZ = 250 --> 10^7
const int K = 10;
T stored[SZ];
int top_pos;
vi trans[SZ];
vi update_poses[5005];
int cur;
bool init_pos[SZ];
T buildSmall(int r){
assert(0 <= r && r < R);
T res;
for(int i = 0; i < C; i++){
for(int j = 0; j < C; j++){
res[i][j] = abs(Hsum[r][i]-Hsum[r][j])+V[r][j];
}
}
return res;
}
void update(int pos){
assert(sz(trans[pos]));
if(trans[pos][0] <= 0){ //individual updates
//remember to negate
stored[pos] = buildSmall(-trans[pos][0]);
if(sz(trans[pos]) > 1){
T ndp;
for(int i = 1; i < sz(trans[pos]); i++){
T small = buildSmall(-trans[pos][i]);
mult(stored[pos], small, ndp);
swap(ndp, stored[pos]);
}
}
}
else{
stored[pos] = stored[trans[pos][0]];
if(sz(trans[pos]) > 1){
T ndp;
for(int i = 1; i < sz(trans[pos]); i++){
mult(stored[pos], stored[trans[pos][i]], ndp);
swap(ndp, stored[pos]);
}
}
}
}
vi initStoredUpdate(int pos){
assert(sz(trans[pos]));
init_pos[pos] = 1;
vi res;
if(trans[pos][0] <= 0){
for(auto u: trans[pos]){
res.pb(-u);
}
}
else{
for(auto u: trans[pos]){
if(!init_pos[u]){
vi add = initStoredUpdate(u);
for(auto x: add){
res.pb(x);
}
}
}
}
update(pos);
for(auto u: res){
update_poses[u].pb(pos);
}
return res;
}
void reBuildHsum(int P){
Hsum[P][0] = 0;
for(int i = 1; i < C; i++){
Hsum[P][i] = Hsum[P][i-1]+H[P][i-1];
}
}
clock_t CL;
db getTime(){
return db(clock()-CL)/db(CLOCKS_PER_SEC);
}
// void buildTransitions(){
// top_pos = ++cur;
// for(int i = 0; i < R; i+=K){
// int this_pos = ++cur;
// assert(cur+5 < SZ);
// trans[top_pos].pb(this_pos);
// for(int j = i; j < min(R, i+K); j++){
// trans[this_pos].pb(-j);
// }
// }
// }
int buildTransitions(int lo = 0, int hi = R-1){
int this_pos = ++cur;
if(lo == 0 && hi == R-1){
top_pos = this_pos;
}
if(hi-lo+1 <= K){
for(int i = lo; i <= hi; i++){
trans[this_pos].pb(-i);
}
}
else{
int M = (lo+hi)/2;
trans[this_pos].pb(buildTransitions(lo, M));
trans[this_pos].pb(buildTransitions(M+1, hi));
}
return this_pos;
}
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
CL = clock();
for(int i = 0; i < 5005; i++){
for(int j = 0; j < 205; j++){
H[i][j] = Hsum[i][j] = V[i][j] = 0;
}
}
top_pos = 0;
for(int i = 0; i < SZ; i++){
trans[i].clear();
}
for(int i = 0; i < 5005; i++){
update_poses[i].clear();
}
cur = 0;
for(int i = 0; i < SZ; i++){
init_pos[i] = 0;
}
#warning clear memory TO 0
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];
}
}
for(int i = 0; i < R; i++){
reBuildHsum(i);
}
//build transitions
buildTransitions();
//cout << "cur: " << cur << "\n";
//#warning assert that SZ is big enough
initStoredUpdate(top_pos);
//cout << getTime() << "\n";
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
reBuildHsum(P);
for(auto u: update_poses[P]){
update(u);
}
//cout << getTime() << "\n";
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
for(auto u: update_poses[P]){
update(u);
}
//cout << getTime() << "\n";
}
int escape(int V1, int V2) {
// for(int i = 0; i < R; i++){
// for(int j = 0; j < C; j++){
// cout << i << " " << j << " " << H[i][j] << " " << V[i][j] << "\n";
// }
// }
return stored[top_pos][V1][V2];
}
