#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cout << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 5e3 + 10;
const int maxm = 200 + 10;
const int sq = 100;
const int inf = 1e9;
int n, m, h[maxn][maxm], v[maxn][maxm], dp[maxn][maxm], val[50][maxm][maxm], seg[210][maxm][maxm];
void change(int v, int l, int r, int idx){
if (l + 1 == r){
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
seg[v][i][j] = val[l][i][j];
}
}
return;
}
int mid = (l + r) >> 1;
if (idx < mid){
change(v << 1, l, mid, idx);
}
else{
change(v << 1 | 1, mid, r, idx);
}
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
seg[v][i][j] = inf;
for (int k = 0; k < m; k++){
seg[v][i][j] = min(seg[v][i][j], seg[v << 1][i][k] + seg[v << 1 | 1][k][j] + ::v[mid*sq-1][k]);
}
}
}
}
inline void update(int r){
for (int i = 1; i < m; i++){
dp[r][i] = min(dp[r][i], dp[r][i-1] + h[r][i-1]);
}
for (int i = m-2; ~i; i--){
dp[r][i] = min(dp[r][i], dp[r][i+1] + h[r][i]);
}
}
inline void build(int blc){
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
if (i == j) dp[blc*sq][j] = 0;
else dp[blc*sq][j] = inf;
}
update(blc*sq);
int idx = min((blc+1)*sq, n) - 1;
for (int j = blc*sq+1; j <= idx; j++){
for (int k = 0; k < m; k++){
dp[j][k] = dp[j-1][k] + v[j-1][k];
}
update(j);
}
for (int j = 0; j < m; j++){
val[blc][i][j] = dp[idx][j];
}
}
change(1, 0, (n-1)/sq+1, blc);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R, m = C;
for (int i = 0; i < n; i++){
for (int j = 0; j < m-1; j++){
h[i][j] = H[i][j];
}
}
for (int i = 0; i < n-1; i++){
for (int j = 0; j < m; j++){
v[i][j] = V[i][j];
}
}
for (int i = 0; i <= (n-1)/sq; i++){
build(i);
}
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
build(P/sq);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
build(P/sq);
}
int escape(int V1, int V2) {
return seg[1][V1][V2];
}
