#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(){
int c = n;
vector< pair<int, int> > last(n, {-1, -1});
vector< vector< pair<int, ll> > > g(c);
vector< tuple<int, int, int> > sky(m);
for(int i = 0; i < m; i++) sky[i] = {y[i], l[i], r[i]};
sort(sky.rbegin(), sky.rend());
set<int> building;
vector< pair<int, int> > build(n);
for(int i = 0; i < n; i++) build[i] = {h[i], i};
sort(build.begin(), build.end());
for(int i = 0; i < m; i++){
while(!build.empty() && build.back().first >= get<0>(sky[i]))
building.insert(build.back().second), build.pop_back();
auto it = building.lower_bound(get<1>(sky[i]));
int prev = -1, ind;
while(it != building.end() && *it <= get<2>(sky[i])){
int pos = *it, hi = get<0>(sky[i]);
it++;
g.resize(c+1);
if(last[pos].first != -1){
g[last[pos].first].push_back({c, last[pos].second-hi});
g[c].push_back({last[pos].first, last[pos].second-hi});
}
last[pos] = {c, hi};
if(prev != -1){
g[ind].push_back({c, x[pos]-x[prev]});
g[c].push_back({ind, x[pos]-x[prev]});
}
prev = pos, ind = c;
c++;
}
}
for(int i = 0; i < n; i++){
if(last[i].first != -1){
g[i].push_back({last[i].first, last[i].second});
g[last[i].first].push_back({i, last[i].second});
}
}
vector<ll> dis(c, INF);
vector<int> vis(c);
priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > q;
dis[s] = 0;
q.push({0, s});
while(!q.empty()){
int u = q.top().second, v;
ll w;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
if(u == e) 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);
return st1();
}
