#include "wombats.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=5010, C=200, T=12, SEGSZ=210*1024*1024/(C*C);
typedef array<array<int, C>, C> DATA;
int n, m, k, u, v, x, y, t, a, b, ans;
int H[MAXN][C], V[MAXN][C];
int L[SEGSZ], R[SEGSZ], ts;
int opt[C][C];
DATA seg[SEGSZ];
inline void _upd(int &x, int y){ if (x>y) x=y;}
void Make(DATA &A, int tl, int tr){
// O(m^2.len)
for (int i=0; i<m; i++) for (int j=0; j<m; j++) A[i][j]=inf;
for (int i=0; i<m; i++) A[i][i]=0;
for (int x=tl; x<tr; x++){
for (int i=0; i<m; i++){
for (int j=1; j<m; j++) _upd(A[i][j], A[i][j-1]+H[x][j-1]);
for (int j=m-1; j; j--) _upd(A[i][j-1], A[i][j]+H[x][j-1]);
}
for (int i=0; i<m; i++) for (int j=0; j<m; j++) A[i][j]+=V[x][j];
}/*
for (int i=0; i<m; i++){
for (int j=1; j<m; j++) _upd(A[i][j], A[i][j-1]+H[tr][j-1]);
for (int j=m-1; j; j--) _upd(A[i][j-1], A[i][j]+H[tr][j-1]);
}*/
}
void Merge(DATA &A, DATA &B, DATA &C){
// O(m^2)
// knuth orz
for (int i=0; i<m; i++) for (int j=0; j<m; j++) C[i][j]=inf;
for (int ij=-m; ij<m; ij++){
for (int i=max(-ij, 0); i<min(m, m-ij); i++){
int j=i+ij; // 0<=j<m
int l=(j?opt[i][j-1]:0);
int r=(i<m-1?opt[i+1][j]:m-1);
for (int k=l; k<=r; k++){
int val=A[i][k]+B[k][j];
if (val<C[i][j]){
C[i][j]=val;
opt[i][j]=k;
}
}
}
}
}
int Build(int tl, int tr){
int id=++ts;
if (tr-tl<=T){
Make(seg[id], tl, tr);
return id;
}
int mid=(tl+tr)>>1;
L[id]=Build(tl, mid);
R[id]=Build(mid, tr);
Merge(seg[L[id]], seg[R[id]], seg[id]);
return id;
}
void Set(int id, int tl, int tr, int pos){
if (pos<tl || tr<=pos) return ;
if (tr-tl<=T){
Make(seg[id], tl, tr);
return ;
}
int mid=(tl+tr)>>1;
Set(L[id], tl, mid, pos);
Set(R[id], mid, tr, pos);
Merge(seg[L[id]], seg[R[id]], seg[id]);
}
void init(int nn, int mm, int HH[5000][200], int VV[5000][200]) {
n=nn;
m=mm;
// assert(m<=20); // 39 point subtask sub124
for (int i=0; i<n; i++) for (int j=0; j+1<m; j++) H[i][j]=HH[i][j];
for (int i=0; i+1<n; i++) for (int j=0; j<m; j++) V[i][j]=VV[i][j];
Build(0, n);
}
void changeH(int P, int Q, int W) {
H[P][Q]=W;
Set(1, 0, n, P);
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
Set(1, 0, n, P);
}
int escape(int V1, int V2){
for (int i=1; i<m; i++) _upd(seg[1][V1][i], seg[1][V1][i-1]+H[n-1][i-1]);
for (int i=m-1; i; i--) _upd(seg[1][V1][i-1], seg[1][V1][i]+H[n-1][i-1]);
return seg[1][V1][V2];
}
