#include "walk.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
using namespace std;
const int MAX=1e6+5;
const ll INF=1LL<<60;
struct ST{
ll s,e,m,d;
ST *l=0,*r=0;
ll p0=-INF,p1=INF,v=0; // set, min
ST(ll s,ll e):s(s),e(e),m((s+e)/2),d(e-s+1){
if (d==1) return;
}
void cc(){
if (d==1) return;
if (!l) l=new ST(s,m);
if (!r) r=new ST(m+1,e);
}
void apl(ll a0,ll a1){
if (a0!=-INF) p0=a0,p1=INF,v=a0;
a1=min(p1,a1),v=min(v,a1);
}
void down(){
if (d>1) l->apl(p0,p1),r->apl(p0,p1);
p0=-INF,p1=INF;
}
ll qry(int x){
if (d==1) return v;
cc();
down();
if (x>m) return r->qry(x);
else return l->qry(x);
}
void upd(int x,int y,ll a0,ll a1){
if (y<x||y<s||x>e) return;
if (x<=s&&y>=e) return apl(a0,a1);
cc();
down();
l->upd(x,y,a0,a1),r->upd(x,y,a0,a1);
}
void upd0(int x,int y,ll a){
upd(x,y,a,INF);
}
void upd1(int x,int y,ll a){
upd(x,y,-INF,a);
}
};
int N,M;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>> pq;
map<pii,int> idx;
ll dst[MAX];
vector<pair<ll,int>> adj[MAX];
vector<ll> hs[MAX];
long long min_distance(vector<int> X,vector<int> H,vector<int> L,vector<int> R,vector<int> Y,int S,int E) {
N=X.size(),M=L.size();
for (int i=0;i<M;i++) for (int x=L[i];x<=R[i];x++) if (Y[i]<=H[x]) hs[x].push_back(Y[i]);
hs[S].push_back(0),hs[E].push_back(0);
for (int i=0;i<N;i++) sort(hs[i].begin(),hs[i].end());
int K=0;
for (int i=0;i<N;i++) for (int x=0;x<hs[i].size();x++) idx[{i,x}]=K++;
for (int i=0;i<N;i++) for (int x=0;x<(int)hs[i].size()-1;x++){
pii a={i,x};
pii b={i,x+1};
ll w=hs[i][x+1]-hs[i][x];
adj[idx[a]].push_back({w,idx[b]}),adj[idx[b]].push_back({w,idx[a]});
}
for (int i=0;i<M;i++){
int pi=L[i];
int p=lower_bound(hs[L[i]].begin(),hs[L[i]].end(),Y[i])-hs[L[i]].begin();
for (int x=L[i]+1;x<=R[i];x++){
int j=lower_bound(hs[x].begin(),hs[x].end(),Y[i])-hs[x].begin();
if (j<hs[x].size()){
pii a={pi,p};
pii b={x,j};
ll w=X[x]-X[pi];
adj[idx[a]].push_back({w,idx[b]}),adj[idx[b]].push_back({w,idx[a]});
p=j;
pi=x;
}
}
}
fill_n(dst,K,INF);
pq.push({0,idx[{S,0}]});
while (pq.size()){
auto [d,pr]=pq.top();
pq.pop();
if (d>=dst[pr]) continue;
dst[pr]=d;
for (auto [w,qr]:adj[pr]){
pq.push({d+w,qr});
}
}
ll ans=dst[idx[{E,0}]];
if (ans==INF) return -1;
return ans;
}
