#include "bits/stdc++.h"
#include "railroad.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll INF = 1e18;
struct DSU{
vector<ll> par,siz;
DSU(ll _n){
par.assign(_n,0);
iota(all(par),0);
siz.assign(_n,1);
}
ll find(ll a){
if(par[a]==a) return a;
return par[a]=find(par[a]);
}
void unite(ll a,ll b){
a = find(a) , b = find(b);
if(a == b) return;
if(siz[a] > siz[b]) swap(a, b);
siz[b] += siz[a];
par[a] = b;
}
};
ll plan_roller_coaster(vector<int> _s, vector<int> _t){
ll n = sz(_s);
array<ll,2> ar[n + 5];
for(ll i = 1; i <= n; i++) ar[i][0] = _s[i], ar[i][1] = _t[i];
ar[0] = {INF,1LL};
vector<ll> zip;
for(ll i=0;i<=n;i++){
zip.push_back(ar[i][0]);
zip.push_back(ar[i][1]);
}
sort(all(zip));
zip.erase(unique(all(zip)),zip.end());
auto Get = [&](ll val) -> ll{
ll it = lower_bound(all(zip),val) - zip.begin();
return it;
};
ll m = sz(zip);
vector<ll> art(m+5,0),eks(m+5,0);
DSU dsu(m+5);
for(ll i = 0; i <= n ; i++){
ll a = Get(ar[i][0]);
art[a]++;
ll b = Get(ar[i][1]);
eks[b]++;
dsu.unite(a,b);
}
ll pa=0,pb=0,ans=0;
for(ll i=0;i<m;i++){
pa += art[i];
pb += eks[i];
if(pa > pb) ans+=(pa-pb)*(zip[i+1]-zip[i]);
if(pa != pb) dsu.unite(i,i+1);
}
vector<array<ll,3>> edges;
for(ll i=0;i+1<m;i++){
if(dsu.find(i)!=dsu.find(i+1)) edges.push_back({zip[i+1]-zip[i],dsu.find(i),dsu.find(i+1)});
}
sort(all(edges));
for(auto x:edges){
if(dsu.find(x[1])!=dsu.find(x[2])){
ans += x[0];
dsu.unite(x[1],x[2]);
}
}
return ans;
}
/*void _(){
ll n; cin >> n;
array<ll,2> ar[n+5];
for(ll i=1;i<=n;i++) cin >> ar[i][0] >> ar[i][1];
ar[0] = {INF,1};
vector<ll> zip;
for(ll i=0;i<=n;i++){
zip.push_back(ar[i][0]);
zip.push_back(ar[i][1]);
}
sort(all(zip));
zip.erase(unique(all(zip)),zip.end());
auto Get = [&](ll val){
ll it = lower_bound(all(zip),val) - zip.begin();
return it;
};
ll m = sz(zip);
vector<ll> art(m+5,0),eks(m+5,0);
DSU dsu(m+5);
for(ll i = 0; i <= n ; i++){
ll a = Get(ar[i][0]);
art[a]++;
ll b = Get(ar[i][1]);
eks[b]++;
dsu.unite(a,b);
}
ll pa=0,pb=0,ans=0;
for(ll i=0;i<m;i++){
pa += art[i];
pb += eks[i];
if(pa > pb) ans+=(pa-pb)*(zip[i+1]-zip[i]);
if(pa != pb) dsu.unite(i,i+1);
}
vector<array<ll,3>> edges;
for(ll i=0;i+1<m;i++){
if(dsu.find(i)!=dsu.find(i+1)) edges.push_back({zip[i+1]-zip[i],i,i+1});
}
sort(all(edges));
for(auto x:edges){
if(dsu.find(x[1])!=dsu.find(x[2])){
ans += x[0];
dsu.unite(x[1],x[2]);
}
}
cout << ans << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
ll tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
