#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSU{
int path[400400];
void init(int n){for (int i=0;i<=n;i++) path[i] = i;}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
bool merge(int s, int v){
s = find(s), v = find(v);
if (s==v) return 0;
path[s] = v;
return 1;
}
}dsu;
int n, deg[400400];
vector<int> a;
long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
n = S.size();
a.push_back(1);
a.push_back(1e9+100);
for (int i=0;i<n;i++) {a.push_back(S[i]); a.push_back(T[i]);}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
dsu.init(a.size());
for (int i=0;i<n;i++){
int x = lower_bound(a.begin(), a.end(), S[i]) - a.begin();
int y = lower_bound(a.begin(), a.end(), T[i]) - a.begin();
deg[x]++;
deg[y]--;
dsu.merge(x, y);
}
ll ans = 0;
for (int i=0;i<(int)a.size()-1;i++){
//printf("%d -> %d\n", a[i], deg[i]);
int target = i?0:1;
if (deg[i]!=target) dsu.merge(i, i+1);
ans += (deg[i] > target)?((ll)(deg[i]-target)*(a[i+1] - a[i])):0LL;
deg[i+1] += deg[i] - target;
deg[i] -= deg[i] - target;
}
vector<pair<int, int>> E;
for (int i=0;i<(int)a.size()-1;i++) if (dsu.find(i) != dsu.find(i+1)){
E.emplace_back(a[i+1] - a[i], i);
}
sort(E.begin(), E.end());
for (auto &[x, y]:E) if (dsu.merge(y, y+1)) ans += x;
return ans;
}
