// M
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
int n;
map < int , int > P;
int Find(int v)
{
return (!P[v] ? 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)
{
n = (int)S.size();
vector < pair < int , int > > A;
for (int i = 0; i < n; i ++)
{
A.push_back({S[i], 1});
A.push_back({T[i], -1});
Merge(S[i], T[i]);
}
A.push_back({(int)(1e9 + 9), 1});
A.push_back({1, -1});
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 * (A[i + 1].first - 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 A[i + 1].first - A[i].first < A[j + 1].first - A[j].first;});
for (int i : R)
if (Merge(A[i].first, A[i + 1].first))
tot += A[i + 1].first - A[i].first;
return tot;
}
