// M
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
const int N = 200005 * 2;
int n, P[N], S[N], T[N];
int Find(int v)
{
return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline bool Merge(int v, int u)
{
v = Find(v);
u = Find(u);
if (v == u)
return 0;
P[v] = u;
return 1;
}
long long plan_roller_coaster(vector < int > _S, vector < int > _T)
{
memset(P, -1, sizeof(P));
n = (int)_S.size();
for (int i = 0; i < n; i ++)
S[i] = _S[i], T[i] = _T[i];
S[n] = (int)(1e9 + 9); T[n] = 1;
vector < int > U;
for (int i = 0; i <= n; i ++)
{
U.push_back(S[i]);
U.push_back(T[i]);
}
sort(U.begin(), U.end());
U.resize(unique(U.begin(), U.end()) - U.begin());
vector < pair < int , int > > A;
for (int i = 0; i <= n; i ++)
{
S[i] = (int)(lower_bound(U.begin(), U.end(), S[i]) - U.begin());
T[i] = (int)(lower_bound(U.begin(), U.end(), T[i]) - U.begin());
A.push_back({S[i], 1});
A.push_back({T[i], -1});
Merge(S[i], T[i]);
}
sort(A.begin(), A.end());
ll Cur = 0, tot = 0;
for (int i = 0; i + 1 < (int)A.size(); i ++)
{
Cur += A[i].second;
if (Cur > 0)
tot += Cur * (U[A[i + 1].first] - U[A[i].first]);
if (Cur)
Merge(A[i].first, A[i + 1].first);
}
vector < int > R((int)A.size() - 1);
iota(R.begin(), R.end(), 0);
sort(R.begin(), R.end(), [&](int i, int j){return U[A[i + 1].first] - U[A[i].first] < U[A[j + 1].first] - U[A[j].first];});
for (int i : R)
if (Merge(A[i].first, A[i + 1].first))
tot += U[A[i + 1].first] - U[A[i].first];
return tot;
}
