#include"walk.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cassert>
#include<stack>
#include<fstream>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
typedef struct st{
ll height,eid;
bool operator<(const st&key)const{
return this->height<key.height;
}
}st;
ll min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g){
int n=x.size(),m=l.size();
set<st> S;
S.insert((st){0,m});
ll dp[100010];
rep(i,m)dp[i]=1e17; dp[m]=0;
vector<ll> app[100010],disapp[100010];
rep(i,m){
app[l[i]].push_back(i);
disapp[r[i]].push_back(i);
}
disapp[0].push_back(m);
rep(i,n){
for(auto id:app[i])S.insert((st){y[id],id});
for(auto id:disapp[i])S.erase((st){y[id],id});
for(auto id:disapp[i]){
auto it=S.lower_bound((st){y[id],id});
if(it!=S.end()){
chmin(dp[it->eid],dp[id]+abs(y[id]-it->height));
}
if(it!=S.begin()){
it--;
chmin(dp[it->eid],dp[id]+abs(y[id]-it->height));
}
}
}
ll ans=1e17;
for(auto id:disapp[n-1])chmin(ans,dp[id]+y[id]);
if(ans==1e17)return -1;
ans+=x[n-1]-x[0];
return ans;
}/*
int main(){
int n,m,s,g;
cin>>n>>m;
vector<int> x(n),h(n),l(m),r(m),y(m);
rep(i,n)cin>>x[i]>>h[i];
rep(i,m)cin>>l[i]>>r[i]>>y[i];
cin>>s>>g;
cout<<min_distance(x,h,l,r,y,s,g)<<endl;
}
*/
