//#include "railroad.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef double ld;
typedef pair<int,int> ii;
typedef tree <ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 4e5 + 5;
int lab[maxn];
int sum[maxn];
vector<int> val;
int n;
int FindLab(int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}
bool Merge(int u , int v){
u = FindLab(u);v = FindLab(v);
if(u == v)return 0;
if(lab[u] > lab[v])swap(u , v);
lab[u] += lab[v];
lab[v] = u;
return 1;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
memset(lab,-1,sizeof lab);
ll res = 0;
n = s.size();
for(int i = 0 ; i < n ; ++i){
val.pb(s[i]);val.pb(t[i]);
}
sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
for(int i = 0 ; i < n ; ++i){
s[i] = lower_bound(val.begin(),val.end(),s[i]) - val.begin();
t[i] = lower_bound(val.begin(),val.end(),t[i]) - val.begin();
Merge(s[i] , t[i]);
sum[s[i]]++;sum[t[i]]--;
}
int cur = 1;
vector<pair<int,int>> edges;
for(int i = (int)val.size() - 1 ; i > 0 ; --i){
cur += sum[i];
if(cur < 0){
res -= 1ll * cur * (val[i] - val[i - 1]);
Merge(i,i-1);
}else if(cur > 0)Merge(i,i-1);
else if(cur == 0)edges.pb(mp(val[i] - val[i - 1] , i));
}
sort(edges.begin(),edges.end());
for(auto & c : edges){
if(Merge(c.second,c.second-1))res += c.first;
}
return res;
}
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// if(fopen(taskname".INP","r")){
// freopen(taskname".INP", "r",stdin);
// freopen(taskname".OUT", "w",stdout);
// }
//
//}
