#include "wombats.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
vector<vector<ll> > v,h; ll R,C;
vector<vector<vector<ll> > > d;
vector<ll> up; vector<ll> ps; vector<ll> val1,val2;
void CalcDist(ll s)
{
REP(i,0,C) {up[i]=INF;} up[s]=0;
ll sum,val;
REP(r,0,R)
{
sum=0LL; ps[0]=0; REP(i,0,C-1) {sum+=h[r][i]; ps[i+1]=sum;}
val=INF;
REP(i,0,C) {val1[i]=val; val=min(val,up[i]-ps[i]);}
val=INF;
for(ll i=C-1;i>=0;i--) {val2[i]=val; val=min(val,up[i]+ps[i]);}
REP(i,0,C)
{
d[s][r][i]=min(up[i],min(val1[i]+ps[i],val2[i]-ps[i])); if(r!=R-1) {up[i]=d[s][r][i]+v[r][i];}
}
}
}
void init(int r, int c, int H[5000][200], int V[5000][200])
{
R=(ll) r; C = (ll) c; vector<ll> xx; REP(i,0,C-1) {xx.pb(0);} REP(i,0,R) {h.pb(xx);} xx.pb(0LL); REP(i,0,R-1) {v.pb(xx);}
REP(i,0,R) {REP(j,0,C-1) {h[i][j]=H[i][j];}}
REP(i,0,R-1) {REP(j,0,C) {v[i][j]=V[i][j];}}
vector<vector<ll> > grid; REP(i,0,R) {grid.pb(xx);} REP(i,0,C) {d.pb(grid);}
REP(i,0,C) {up.pb(INF);} REP(i,0,C) {ps.pb(0LL); val1.pb(0LL); val2.pb(0LL);}
REP(i,0,C) {CalcDist(i);}
return;
}
void changeH(int p, int q, int W)
{
h[p][q]=W; REP(i,0,C) {CalcDist(i);}
}
void changeV(int p, int q, int W)
{
v[p][q]=W; REP(i,0,C) {CalcDist(i);}
}
int escape(int v1, int v2)
{
return d[v1][R-1][v2];
}
