#include <bits/stdc++.h>
#include "walk.h"
#pragma GCC optimize("O3")
#define ll long long
using namespace std;
const int N = 100000;
const ll INF = numeric_limits<ll>::max()/4;
int n, m, s, e;
int x[N], h[N], l[N], r[N], y[N];
ll st1(){
map< int, set< pair<int, int> > > mp;
vector<int> yv;
for(int i = 0; i < m; i++){
if(!mp.count(y[i])) yv.push_back(y[i]);
mp[y[i]].insert({l[i], r[i]});
}
sort(yv.begin(), yv.end());
m = yv.size();
vector< vector< pair<int, ll> > > g(n*(m+1));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(h[i] < yv[j]) break;
if(j) g[i*(m+1)+j].push_back({i*(m+1)+j-1, yv[j]-yv[j-1]});
else g[i*(m+1)+j].push_back({i*(m+1)+m, yv[j]});
if(j < m-1) g[i*(m+1)+j].push_back({i*(m+1)+j+1, yv[j+1]-yv[j]});
auto it = mp[yv[j]].lower_bound({i, 0});
if(it != mp[yv[j]].end() && it->first == i){
int nxt = i+1;
for(; h[nxt] < yv[j]; nxt++);
g[i*(m+1)+j].push_back({nxt*(m+1)+j, x[nxt]-x[i]});
}
if(it != mp[yv[j]].begin() && (--it)->second >= i){
int nxt = i-1;
for(; h[nxt] < yv[j]; nxt--);
g[i*(m+1)+j].push_back({nxt*(m+1)+j, x[i]-x[nxt]});
if(it->second > i){
nxt = i+1;
for(; h[nxt] < yv[j]; nxt++);
g[i*(m+1)+j].push_back({nxt*(m+1)+j, x[nxt]-x[i]});
}
}
}
g[i*(m+1)+m].push_back({i*(m+1), yv[0]});
}
vector<ll> dis(n*(m+1), INF);
vector<int> vis(n*(m+1));
priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > q;
dis[s*(m+1)+m] = 0;
q.push({0, s*(m+1)+m});
while(!q.empty()){
int u = q.top().second, v;
ll w;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
if(u == e*(m+1)+m) return dis[u];
for(auto &t : g[u]){
tie(v, w) = t;
if(dis[v] > dis[u]+w){
dis[v] = dis[u]+w;
q.push({dis[v], v});
}
}
}
return -1;
}
void wrt(vector<int>& X, vector<int>& H, vector<int>& L, vector<int>& R, vector<int>& Y, int S, int G){
for(int i = 0; i < n; i++) x[i] = X[i], h[i] = H[i];
for(int i = 0; i < m; i++) l[i] = L[i], r[i] = R[i], y[i] = Y[i];
s = S, e = G;
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
n = x.size(), m = y.size();
wrt(x, h, l, r, y, s, g);
if(n <= 50 && m <= 50) return st1();
return 0;
}
