#include "bits/stdc++.h"
#include "wombats.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll C = 205;
const ll R = 5095;
const ll BL = 130;
const ll INF = 3000000005;
ll dp[4*(R/BL)][C][C],H[R][C],V[R][C],Lf[R],Rg[R],n,m;
ll Old[C][C],New[C][C],Index[R];
inline void upd_block(ll ind){
for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) Old[i][j] = New[i][j] = INF;
for(ll i=0;i<m;i++){
ll cur = 0;
Old[i][i] = V[Lf[ind]][i];
for(ll j=i-1;j>=0;j--){
cur += H[Lf[ind]][j];
Old[i][j] = cur + V[Lf[ind]][j];
}
cur = 0;
for(ll j=i+1;j<m;j++){
cur += H[Lf[ind]][j-1];
Old[i][j] = cur + V[Lf[ind]][j];
}
}
for(ll z=Lf[ind]+1;z<=Rg[ind];z++){
for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) New[i][j] = INF;
for(ll i=0;i<m;i++){
ll hm = INF,cur_sum = 0;
for(ll j=0;j<m;j++){
hm = min(hm, Old[i][j] - cur_sum);
New[i][j] = min(New[i][j], V[z][j] + hm + cur_sum);
cur_sum += H[z][j];
}
hm = INF,cur_sum = 0;
for(ll j=m-1;j>=0;j--){
hm = min(hm, Old[i][j] - cur_sum);
New[i][j] = min(New[i][j], V[z][j] + hm + cur_sum);
cur_sum += H[z][j];
}
}
for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) Old[i][j] = New[i][j];
}
for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) dp[Index[ind]][i][j] = Old[i][j];
}
inline void merge(ll rt){
for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) dp[rt][i][j] = INF;
for(ll i=0;i<C;i++)
for(ll j=0;j<C;j++)
for(ll k=0;k<C;k++)
dp[rt][i][k] = min(dp[rt][i][k], dp[rt*2][i][j] + dp[rt*2+1][j][k]);
}
void Find(ll rt,ll l,ll r){
if(l==r){
Index[l] = rt;
return;
}
ll mid=(l+r)/2;
Find(rt*2,l,mid),Find(rt*2+1,mid+1,r);
}
void build(ll rt,ll l,ll r){
if(l==r) return;
ll mid=(l+r)/2;
build(rt*2,l,mid),build(rt*2+1,mid+1,r);
merge(rt);
}
inline void upd(ll rt){
while(rt){
merge(rt);
rt/=2;
}
}
void init(int _r, int _c, int _H[5000][200], int _V[5000][200]){
n = _r, m = _c;
for(ll i=0;i<n;i++){
ll u = i / BL;
Rg[u] = i;
if(i % BL == 0) Lf[u] = i;
}
for(ll i=0;i<n;i++) for(ll j=0;j+1<m;j++) H[i][j] = _H[i][j];
for(ll i=0;i+1<n;i++) for(ll j=0;j<m;j++) V[i][j] = _V[i][j];
Find(1,0,(n-1)/BL);
for(ll i=0;i<=(n-1)/BL;i++) upd_block(i);
build(1,0,(n-1)/BL);
}
void changeH(int P, int Q, int W){
H[P][Q] = W;
upd_block(P/BL);
//upd(Index[P/BL]/2);
}
void changeV(int P, int Q, int W){
V[P][Q] = W;
upd_block(P/BL);
//upd(Index[P/BL]/2);
}
int escape(int V1, int V2){
return (int) dp[1][V1][V2];
}
