#include "railroad.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 400010;
vector<int> A[N];
int vis[N];
void dfs(int v, int c)
{
vis[v] = c;
for (int u : A[v])
if (vis[u] == -1)
dfs(u, c);
}
namespace dsu {
int par[N];
int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
bool unite(int v, int u) {
v = rt(v);
u = rt(u);
if (v == u)
return 0;
par[u] = v;
return 1;
}
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
s.push_back(1e9+10);
t.push_back(1);
int n = s.size();
vector<int> cmp;
Loop (i,0,n) {
cmp.push_back(s[i]);
cmp.push_back(t[i]);
}
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
int m = cmp.size();
vector<int> val(m);
Loop (i,0,n) {
int x = lower_bound(cmp.begin(), cmp.end(), s[i]) - cmp.begin();
int y = lower_bound(cmp.begin(), cmp.end(), t[i]) - cmp.begin();
A[x].push_back(y);
A[y].push_back(x);
val[x]--;
val[y]++;
}
int cnt = 0;
ll ans = 0;
Loop (i,0,m-1) {
cnt += val[i];
if (cnt < 0)
ans += (ll)(cmp[i+1] - cmp[i]) * -cnt;
if (cnt) {
A[i].push_back(i+1);
A[i+1].push_back(i);
}
}
int k = 0;
memset(vis, -1, sizeof(vis));
Loop (i,0,m) {
if (vis[i] == -1)
dfs(i, k++);
}
memset(dsu::par, -1, sizeof(dsu::par));
vector<tuple<int,int,int>> E;
Loop (i,0,m-1)
E.push_back({cmp[i+1] - cmp[i], vis[i], vis[i+1]});
sort(E.begin(), E.end());
for (auto [w, v, u] : E) {
if (dsu::unite(v, u)) {
ans += w;
}
}
return ans;
}
