//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include "wombats.h"
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e9;
const int Q = 2e5+50,B = 15;
int N,c;
using Matrix = int[201][201];
int sag[5000][200],as[5000][2000];
Matrix d;
void man(int l,int r) {
for (int i=0;i<c;i++) for (int j=0;j<c;j++) d[i][j] = inf;
for (int i=0;i<c;i++) {
d[i][i] = 0;
for (int j=i+1;j<c;j++) d[i][j] = d[j][i] = d[i][j-1]+sag[l-1][j-1];
}
for (int p=l+1;p<=r;p++) {
for (int s = 0;s<c;s++) {
for (int j=0;j<c;j++) {
d[s][j] = d[s][j]+as[p-2][j];
if (j) d[s][j] = min(d[s][j],d[s][j-1]+sag[p-1][j-1]);
}
for (int j=c-2;j>=0;j--){
d[s][j] = min(d[s][j],d[s][j+1]+sag[p-1][j]);
}
}
}
}
struct ST {
Matrix dp[5000];
void build(int node,int l,int r) {
if (l+B-1 >= r) {
//BC^2
man(l,r);
for (int i=0;i<c;i++) {
for (int j=0;j<c;j++) dp[node][i][j] = d[i][j];
}
return;
}
int m = (l+r) >> 1;
build(2*node,l,m);
build(2*node+1,m+1,r);
for (int i=0;i<c;i++) {
for (int j=0;j<c;j++) {
dp[node][i][j] = inf;
for (int k=0;k<c;k++) {
dp[node][i][j] = min(dp[node][i][j],
dp[2*node][i][k]+dp[2*node+1][k][j]+as[m-1][k]);
}
}
}
}
void update(int node,int l,int r,int p) {
if (l+B-1 >= r) {
//BC^2
man(l,r);
for (int i=0;i<c;i++) {
for (int j=0;j<c;j++) dp[node][i][j] = d[i][j];
}
return;
}
int m = (l+r) >> 1;
if (p<=m) update(2*node,l,m,p);
else update(2*node+1,m+1,r,p);
for (int i=0;i<c;i++) {
for (int j=0;j<c;j++) {
dp[node][i][j] = inf;
for (int k=0;k<c;k++) {
dp[node][i][j] = min(dp[node][i][j],
dp[2*node][i][k]+dp[2*node+1][k][j]+as[m-1][k]);
}
}
}
}
} st;
void init(int32_t R, int32_t C, int32_t H[5000][200], int32_t V[5000][200]) {
N = R,c = C;
for (int i=0;i<N;i++) {
for (int j=0;j<c-1;j++) sag[i][j] = H[i][j];
if (i<N-1) for (int j=0;j<c;j++) as[i][j] = V[i][j];
};
st.build(1,1,N);
}
void changeH(int32_t P, int32_t Q, int32_t W) {
sag[P][Q] = W;
st.update(1,1,N,P+1);
}
void changeV(int32_t P, int32_t Q, int32_t W) {
as[P][Q] = W;
st.update(1,1,N,P+1);
}
int32_t escape(int32_t V1, int32_t V2) {
return st.dp[1][V1][V2];
}
