#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+10;
ll dsu[MAXN];
bool f(ll x){
if (dsu[x] < 0)return x;
return (dsu[x] = f(dsu[x]));
}
bool join(ll x,ll y){
x = f(x),y = f(y);
if (x != y){
if (dsu[x] > dsu[y])swap(x,y);
dsu[x] += dsu[y];
dsu[y] = x;
return 1;
}
return 0;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
memset(dsu,-1,sizeof dsu);
s.push_back(1e9);
t.push_back(1);
int n = (int) s.size();
vector <ll> val;
for (ll i = 0;i < n;i ++){
val.push_back(s[i]);
val.push_back(t[i]);
}
sort(val.begin(),val.end());
val.resize(unique(val.begin(),val.end())-val.begin());
vector <ll> cnt(sz(val));
for (ll i = 0;i < n;i ++){
ll l = lower_bound(val.begin(),val.end(),s[i])-val.begin();
ll r = lower_bound(val.begin(),val.end(),t[i])-val.begin();
join(l,r);
cnt[l]++,cnt[r]--;
}
for (ll i = 1;i < sz(val);i ++){
cnt[i] += cnt[i-1];
}
ll res = 0;
vector <pll> edges;
for (ll i = 0;i + 1 < sz(val);i ++){
if (cnt[i] != 0)join(i,i+1);
else {
edges.push_back(MP(val[i+1]-val[i],i));
}
res += max(0LL,cnt[i]) * (val[i+1]-val[i]);
}
sort(edges.begin(),edges.end());
for (auto x:edges){
if (join(x.se,x.se+1)){
res += x.fi;
}
}
return res;
}
