#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>
#define _all(T) T.begin(),T.end()
#define tiii tuple<int,int,int>
const ll inf = 1e9+10;
const int mxn = 2e5+10;
struct DSU{
int dsu[mxn*3],sz[mxn*3];
void init(int n){
iota(dsu,dsu+n,0);
fill(sz,sz+n,1);
}
int root(int k){return k== dsu[k]?k:dsu[k] = root(dsu[k]);}
void onion(int a,int b){
a = root(a),b = root(b);
if(a == b)return;
if(sz[a]<sz[b])swap(a,b);
sz[a] += sz[b];
dsu[b] = a;
return;
}
DSU(){}
};
DSU dsu;
vector<int> all;
int deg[mxn*3];
int in[mxn*3],out[mxn*3];
vector<tuple<int,int,int>> edges;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
ll ans = 0;
int N = (int)s.size();
all.push_back(0);
for(int i = 0;i<N;i++){
all.push_back(s[i]);
all.push_back(t[i]);
}
all.push_back(inf);
sort(_all(all));all.erase(unique(_all(all)),all.end());
dsu.init(all.size());
for(int i = 0;i<N;i++){
s[i] = lower_bound(_all(all),s[i])-all.begin();
t[i] = lower_bound(_all(all),t[i])-all.begin();
out[s[i]]++;
in[t[i]]++;
dsu.onion(s[i],t[i]);
}
in[0]++;out[all.size()-1]++;
for(int i = 0;i<all.size();i++){
if(i != all.size()-1||in[i] == out[i]);
if(in[i] == out[i])continue;
else if(in[i]<out[i]){
int d = out[i]-in[i];
ans += 1ll*(all[i+1]-all[i])*d;
in[i] += d;
out[i+1] += d;
dsu.onion(i,i+1);
}
else{
int d = in[i]-out[i];
out[i] += d;
in[i+1] += d;
dsu.onion(i,i+1);
}
}
for(int i = 1;i<all.size();i++){
if(dsu.root(i) != dsu.root(i-1)){
edges.push_back(tiii(all[i]-all[i-1],i,i-1));
}
}
sort(edges.begin(),edges.end());
for(auto &[w,a,b]:edges){
if(dsu.root(a) != dsu.root(b)){
dsu.onion(a,b);
ans += w;
}
}
return ans;
}
