//Challenge: Accepted
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r)cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define maxv 1200005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<60;
vector<pii> adj[maxv];
ll dis[maxv];
int prv[maxn], px[maxn];
vector<pii> seg[maxn];
bool on[maxn];
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int st, int ed) {
int n = X.size(), m = L.size();
for (int i = 0;i < m;i++) {
for (int j = L[i];j <= R[i];j++) {
seg[j].push_back({Y[i], i});
}
}
for (int i = 0;i < n;i++) sort(seg[i].begin(), seg[i].end());
auto addedge = [&] (int u, int v, int w){
adj[u].push_back({v, w});
adj[v].push_back({u, w});
debug(u, v, w);
};
int term = maxv - 1;
{
int cur = 1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < seg[i].size();j++) {
int id = seg[i][j].ss;
int y = Y[id], node = cur++;
if (i == st && y <= H[i]) addedge(node, 0, y);
if (i == ed && y <= H[i]) addedge(node, term, y);
if (on[id]) {
addedge(node, prv[id], X[i] - px[id]);
} else {
on[id] = 1;
}
if (j && y <= H[i]) addedge(node, node-1, y - seg[i][j-1].ff);
prv[id] = node;
px[id] = X[i];
}
}
}
for (int i = 0;i < maxv;i++) dis[i] = inf;
dis[0] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push({0, 0});
while (pq.size()) {
auto [d, cur] = pq.top();
pq.pop();
if (d != dis[cur]) continue;
for (auto [v, w]:adj[cur]) {
if (d + w < dis[v]) {
dis[v] = d + w;
pq.push({dis[v], v});
}
}
}
if (dis[term] == inf) return -1;
return dis[term];
}
