#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int MAXN = 4e5 + 7;
int s[MAXN], t[MAXN], n, in[MAXN], out[MAXN], fa[MAXN];
vector<int> val;
void change(int &n)
{
n = lower_bound(val.begin(), val.end(), n) - val.begin();
}
int root(int u)
{
if (fa[u] < 0) return u;
return fa[u] = root(fa[u]);
}
void join(int u, int v)
{
u = root(u), v = root(v);
if (u != v) fa[u] = v;
}
ll plan_roller_coaster(vector<int> s, vector<int> t)
{
// freopen("test.INP","r",stdin);
// freopen("BAILAM.OUT","w",stdout);
// io;
n = (int)s.size();
for (int i = 0; i < n; ++i)
{
val.push_back(s[i]);
val.push_back(t[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
int sz = (int)val.size();
for (int i = 0; i < sz; ++i) fa[i] = -1;
++out[sz - 1], ++in[0];
join(0, sz - 1);
for (int i = 0; i < n; ++i)
{
change(s[i]);
change(t[i]);
++out[s[i]], ++in[t[i]];
join(s[i], t[i]);
}
ll res = 0;
for (int i = sz - 1; i > 0; --i)
{
if (out[i] != in[i]) join(i, i - 1);
while (out[i] > in[i]) ++in[i], ++out[i - 1];
while (out[i] < in[i]) ++out[i], ++in[i - 1], res += (val[i] - val[i - 1]);
}
vector< pair<int, pair<int,int> > > ed;
for (int i = 0; i < sz - 1; ++i) ed.push_back({val[i + 1] - val[i], {i, i + 1}});
// for (int i = 0; i < sz; ++i) cout << i << ' ' << val[i] << ' ' << root(i) << '\n';
sort(ed.begin(), ed.end());
for (auto it: ed)
{
int u = root(it.se.fi), v = root(it.se.se), cost = it.fi;
if (u != v)
{
res += cost;
fa[u] = v;
}
}
// cout << res;
return res;
}
