#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j ; i < (int)k; i++)
inline bool smin(int &l, int r) {
if (r < l) return l = r, true;
return false;
}
inline bool smax(int &l ,int r) {
if (l < r) return l = r , true;
return false;
}
const int LEN = 35;
const int MAXN = 5000 / LEN + 10;
int R , C;
int dist[MAXN][2][202][202];
int H[5000][200];
int V[5000][200];
struct segment {
int d[202][202];
segment() {
memset(d , 63 , sizeof(d));
}
} seg[MAXN << 2];
void solve(int So , int Z, const segment &L, const segment &R , segment &res, int l , int r, int s , int t) {
if (l >= r) return;
int mid = l + r >> 1;
int best = s;
int val = 1e9 + 10;
rep(i , s , t + 1)
if (smin(val , L.d[So][i] + V[Z][i] + R.d[i][mid]))
best = i;
res.d[So][mid] = val;
solve(So , Z , L , R , res , l , mid , s , best);
solve(So , Z , L , R , res , mid + 1 , r , best , t);
}
inline void merge(segment &res , const segment &l, const segment &r, int mid) {
rep(so , 0 , C)
solve(so, mid * LEN - 1 , l , r , res, 0 , C, 0 , C - 1);
}
void build(int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
// cout << "LETS BUILD : " << l << ' ' << r << endl;
if (l == r - 1) {
rep(i , 0 , C)
rep(j , 0 , C)
seg[id].d[i][j] = dist[l][0][i][j];
return;
}
int mid = l + r >> 1;
build(l , mid , id << 1);
build(mid , r ,id << 1 | 1);
merge(seg[id] , seg[id << 1] , seg[id << 1 | 1] , mid);
}
void segUpt(int pos , int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
if (l == r - 1) {
rep(i , 0 , C)
rep(j , 0 , C)
seg[id].d[i][j] = dist[l][0][i][j];
return;
}
int mid = l +r >> 1;
if (pos < mid) segUpt(pos , l, mid , id << 1);
else segUpt(pos , mid , r, id << 1 | 1);
merge(seg[id] , seg[id << 1] , seg[id << 1 | 1] , mid);
}
inline void build_len(int id) {
memset(dist[id] , 63 , sizeof(dist[id]));
rep(i , 0 , C) {
dist[id][0][i][i] = 0;
rep(j , i + 1, C)
dist[id][0][i][j] = dist[id][0][j][i] = dist[id][0][i][j - 1] + H[id * LEN][j - 1];
}
for (int i = id * LEN + 1; i < min(R , (id + 1) * LEN); i++) {
memset(dist[id][1] , 63 , sizeof(dist[id][1]));
rep(x , 0 , C) {
for (int y = 0; y < C; y++) {
smin(dist[id][1][x][y] , dist[id][0][x][y] + V[i - 1][y]);
if (y)
smin(dist[id][1][x][y] , dist[id][1][x][y - 1] + H[i][y - 1]);
}
for (int y = C - 1; ~y; y--)
if (y + 1 != C)
smin(dist[id][1][x][y] , dist[id][1][x][y + 1] + H[i][y]);
}
/*
rep(x , 0 , C)
rep(y , 0 , C)
cout << ' ' << x << ' '<< y << ' ' << dist[id][0][x][y] << endl;
cout << endl;
*/
rep(x , 0 , C) rep(y , 0 , C) dist[id][0][x][y] = dist[id][1][x][y];
}
/*
rep(x , 0 , C)
rep(y , 0 , C)
cout << ' ' << x << ' '<< y << ' ' << dist[id][0][x][y] << endl;
*/
}
void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) {
R = R_ , C = C_;
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];
for (int i = 0; i * LEN < R; i++)
build_len(i);
build();
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
build_len(P / LEN);
segUpt(P / LEN);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
build_len((P + 1) / LEN);
segUpt(P / LEN);
}
int escape(int V1, int V2) {
return seg[1].d[V1][V2];
}
/*
int main() {
int r , c;
cin >> r >> c;
rep(i , 0 , r)
rep(j , 0 , c - 1)
cin >> H[i][j];
rep(i , 0 , r - 1)
rep(j , 0 , c)
cin >> V[i][j];
init(r , c , H , V);
int e;
cin >> e;
while (e--) {
int tp;
cin >> tp;
if (tp == 3) {
int x , y;
cin >> x >> y;
cout << escape(x , y) << endl;
}
else if (tp == 1) {
int x , y , w;
cin >> x >> y >> w;
changeH(x ,y , w);
}
else {
int x , y , w;
cin >> x >> y >> w;
changeV(x ,y , w);
}
}
return 0;
}
*/
