//In the name of God
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll dsu[maxn], sz[maxn], ps[maxn];
ll par(ll v){
if(dsu[v] != v) dsu[v] = par(dsu[v]);
return dsu[v];
}
bool Union(ll v, ll u){
v = par(v);
u = par(u);
if(u == v) return 0;
if(sz[v] < sz[u]) swap(v, u);
sz[v] += sz[u];
dsu[u] = v;
return 1;
}
long long plan_roller_coaster(vector<int> s, vector<int> t){
for(ll i = 0; i < maxn; i++){
dsu[i] = i;
sz[i] = 1;
}
s.pb(inf + 10);
t.pb(0);
ll n = Sz(s);
vector<ll> vec;
for(ll i = 0; i < n; i++){
vec.pb(s[i]);
vec.pb(t[i]);
}
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
for(ll i = 0; i < n; i++){
s[i] = lower_bound(all(vec), s[i]) - vec.begin();
t[i] = lower_bound(all(vec), t[i]) - vec.begin();
Union(s[i], t[i]);
ps[s[i] + 1]++;
ps[t[i] + 1]--;
}
vector<pll> e;
ll ans = 0;
for(ll i = 1; i < Sz(vec); i++){
ps[i] += ps[i - 1];
if(ps[i] > 0) ans += ps[i] * (vec[i] - vec[i - 1]);
if(ps[i] == 0) e.pb(Mp(vec[i] - vec[i - 1], i));
else Union(i - 1, i);
}
sort(all(e));
for(pll i : e){
if(Union(i.S, i.S - 1)){
ans += i.F;
}
}
return ans;
}
/*int main(){
fast_io;
return 0;
}*/
