#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=600000+10;
vector<long long>allind;
long long n,vorod[maxn],khoroj[maxn],inf=1e9+5;
struct dsu{
long long par[maxn];
dsu(){
for(long long i=0;i<maxn;i++){
par[i]=i;
}
}
long long root(long long u){
if(u==par[u]){
return u;
}
return par[u]=root(par[u]);
}
long long con(long long u,long long v){
u=root(u);v=root(v);
if(u==v){
return 0;
}
par[u]=v;
return 1;
}
}ds,ds2;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
s.push_back(inf);
t.push_back(1);
n=(long long)s.size();
for(long long i=0;i<n;i++){
allind.push_back(s[i]);
allind.push_back(t[i]);
}
sort(allind.begin(),allind.end());
allind.resize(unique(allind.begin(),allind.end())-allind.begin());
for(long long i=0;i<n;i++){
long long pp=lower_bound(allind.begin(),allind.end(),s[i])-allind.begin();
khoroj[pp]++;
long long p=lower_bound(allind.begin(),allind.end(),t[i])-allind.begin();
vorod[p]++;
ds.con(p,pp);
}
long long mainres=0,vo=0,ko=0;
for(long long i=0;i<(long long)allind.size();i++){
ko+=khoroj[i];
vo+=vorod[i];
if(ko>vo){
mainres+=(ko-vo)*(allind[i+1]-allind[i]);
}
if(ko!=vo){
ds.con(i,i+1);
}
}
vector<pair<long long ,pair<long long ,long long>>>allv;
for(long long i=0;i<(long long)allind.size()-1;i++){
if(ds.root(i)!=ds.root(i+1)){
allv.push_back(make_pair(allind[i+1]-allind[i],make_pair(ds.root(i),ds.root(i+1))));
}
}
sort(allv.begin(),allv.end());
for(long long i=0;i<(long long)allv.size();i++){
if(ds2.con(allv[i].second.first,allv[i].second.second)){
mainres+=allv[i].first;
}
}
return mainres;
}
