// In the name of Allah
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 7;
const ll oo = 1e18 + 4;
const int maxlg = 20;
int n, m, sz, ux, vx;
pii A[maxn]; pair<pii, int> Q[maxn];
vector<pll> adj[maxn]; ll dis[maxn];
vector<int> arr, ls1[maxn], ls2[maxn];
set<int> st; int cnt[maxn];
priority_queue<pll> qu; int mark[maxn];
vector<int> ls[maxn]; int ind[maxn];
pll rmq[maxn][maxlg];
int GI(int x) {
return lower_bound(all(arr), x) - arr.begin();
}
ll calx(int j) {
ll res = oo;
auto it = st.lower_bound(j);
if (it != st.end()) {
int w = (*it);
res = min(res, dis[w] + (arr[w] - arr[j]));
}
if (it != st.begin()) {
it--; int w = (*it);
res = min(res, dis[w] + (arr[j] - arr[w]));
}
return res;
}
ll solvex() {
arr.pb(0);
for (int i = 0; i < m; i++) {
int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
arr.pb(x);
}
sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
for (int i = 0; i < m; i++) {
int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
int j = GI(x); ls1[l].pb(j); ls2[r].pb(j);
}
fill(dis, dis + len(arr), oo); fill(cnt, cnt + len(arr), 0);
for (int i = 0; i < n - 1; i++) {
for (int j : ls1[i]) {
cnt[j]++;
if (cnt[j] == 1) {
if (i == 0) dis[j] = arr[j];
else dis[j] = calx(j);
st.insert(j);
}
}
for (int j : ls2[i]) {
cnt[j]--;
if (cnt[j] == 0) {
dis[j] = oo; st.erase(j);
}
}
}
ll res = calx(0) + (A[n - 1].F - A[0].F);
if (res >= oo) return -1;
return res;
}
int GIx(int u, int x) {
int j = lower_bound(all(ls[u]), x) - ls[u].begin();
return ind[u] + j;
}
pll get_max(int l, int r) {
if (r - l <= 0) return Mp(-oo, -1);
int j = __lg(r - l);
return max(rmq[l][j], rmq[r - (1 << j)][j]);
}
void addE(int u, int v, ll w) {
adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w));
}
void addx(int l, int r, int x) {
if (r - l <= 1) return ;
auto f = get_max(l + 1, r - 1);
if (f.F >= x) {
addx(l, f.S + 1, x); addx(f.S, r, x);
}
else {
ls[l].pb(x); ls[r - 1].pb(x);
}
}
void adde(int l, int r, int x) {
if (r - l <= 1) return ;
auto f = get_max(l + 1, r - 1);
if (f.F >= x) {
adde(l, f.S + 1, x); adde(f.S, r, x);
}
else {
addE(GIx(l, x), GIx(r - 1, x), (A[r - 1].F - A[l].F));
}
}
void dij(int v) {
fill(dis, dis + sz, oo); fill(mark, mark + sz, 0);
dis[v] = 0; qu.push(Mp(-dis[v], v));
while (!qu.empty()) {
int v = qu.top().S; qu.pop();
if (mark[v]) continue;
mark[v] = 1;
for (auto f : adj[v]) {
int u = f.F; ll w = f.S;
if (dis[v] + w < dis[u]) {
dis[u] = dis[v] + w;
qu.push(Mp(-dis[u], u));
}
}
}
}
ll solve() {
for (int i = n - 1; i >= 0; i--) {
rmq[i][0] = Mp(A[i].S, i);
for (int j = 1; j < maxlg; j++) {
if (i + (1 << j) - 1 >= n) break;
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
ls[ux].pb(0); ls[vx].pb(0);
for (int i = 0; i < m; i++) {
int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
addx(l, r + 1, x);
}
sz = 0;
for (int i = 0; i < n; i++) {
sort(all(ls[i])); ls[i].resize(unique(all(ls[i])) - ls[i].begin());
if (i - 1 >= 0) ind[i] = ind[i - 1] + len(ls[i - 1]);
else ind[i] = 0;
for (int j = 1; j < len(ls[i]); j++) {
addE(ind[i] + (j - 1), ind[i] + j, ls[i][j] - ls[i][j - 1]);
}
sz += len(ls[i]);
}
for (int i = 0; i < m; i++) {
int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
adde(l, r + 1, x);
}
int u = GIx(ux, 0), v = GIx(vx, 0); dij(u);
if (dis[v] >= oo) return -1;
return dis[v];
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = len(x); m = len(l); ux = s; vx = g;
if (ux > vx) swap(ux, vx);
for (int i = 0; i < n; i++) {
A[i] = Mp(x[i], h[i]);
}
for (int i = 0; i < m; i++) {
Q[i] = Mp(Mp(l[i], r[i]), y[i]);
}
if (ux == 0 && vx == n - 1) return solvex();
else return solve();
}
