#include<bits/stdc++.h>
#include "walk.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 1e5 ;
vector<ll> all[N + 1] ;
vector<pair<ll, ll>> v[10 * N + 1] ;
ll dist[10 * N + 1] ;
ll deikstra(ll fr, ll to)
{
for(ll i = 0 ; i < 10 * N ; i++)
dist[i] = 1e18 ;
set<pair<ll, ll>> s ;
s.insert({0, fr}) ;
dist[fr] = 0 ;
while(s.size())
{
ll city = (*s.begin()).se, ds = (*s.begin()).fi ;
s.erase(s.begin()) ;
if(ds > dist[city])
continue ;
for(auto i : v[city])
{
if(dist[i.fi] <= ds + i.se)
continue ;
dist[i.fi] = ds + i.se ;
s.insert({dist[i.fi], i.fi}) ;
}
}
return dist[to] ;
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
ll n = x.size(), m = l.size(), ans = 0 ;
if(x.size() <= 50 && l.size() <= 50)
{
ll cnt = 0 ;
map<pair<ll, ll>, ll> mp ;
set<pair<ll, ll>> st ;
st.insert({0, s}) ;
st.insert({0, g}) ;
for(ll j = 0 ; j < m ; j++)
{
for(ll q = l[j] ; q <= r[j] ; q++)
if(h[q] >= y[j])
st.insert({y[j], q}) ;
}
for(auto i : st)
{
all[i.se].push_back(i.fi) ;
cnt++ ;
mp[i] = cnt ;
}
for(ll i = 0 ; i < n ; i++)
for(ll j = 0 ; j < all[i].size() ; j++)
for(ll q = j + 1 ; q < all[i].size() ; q++)
{
ll to = mp[{all[i][j], i}], fr = mp[{all[i][q], i}] ;
if(to == fr)
continue ;
v[fr].push_back({to, abs(all[i][j] - all[i][q])}) ;
v[to].push_back({fr, abs(all[i][j] - all[i][q])}) ;
}
for(ll i = 0 ; i < n ; i++)
for(ll j = 0 ; j < m ; j++)
{
if(y[j] > h[i] || i < l[j] || i > r[j])
continue ;
ll fr = mp[{y[j], i}] ;
for(ll q = i + 1 ; q <= r[j] ; q++)
if(h[q] >= y[j])
{
ll to = mp[{y[j], q}] ;
v[fr].push_back({to, abs(x[i] - x[q])}) ;
v[to].push_back({fr, abs(x[i] - x[q])}) ;
}
}
ans = deikstra(mp[{0, s}], mp[{0, g}]) ;
if(ans == 1e18)
ans = -1 ;
return ans ;
}
}
//signed main()
//{
// ios_base::sync_with_stdio( 0 ) ;
// cin.tie( 0 ) ;
// cout.tie( 0 ) ;
// int n, m, s, g ;
// cin >> n >> m ;
// vector<int> x(n), h(n), l(m), r(m), y(m) ;
// for(int i = 0 ; i < n ; i++)
// cin >> x[i] >> h[i] ;
// for(int i = 0 ; i < m ; i++)
// cin >> l[i] >> r[i] >> y[i] ;
// cin >> s >> g ;
// cout << min_distance(x, h, l, r, y, s, g) ;
// return 0 ;
//}
