#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)
//int main()
{
// freopen("test.INP","r",stdin);
// freopen("BAILAM.OUT","w",stdout);
// io;
n = (int)s.size();
// cin >> n;
for (int i = 0; i < n; ++i)
{
// cin >> s[i] >> t[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]);
}
vector< pair<int, pair<int,int> > > ed;
ll res = 0;
for (int i = sz - 1; i > 0; --i)
{
if (out[i] != in[i])
{
join(i, i - 1);
if (out[i] > in[i]) out[i - 1] += (out[i] - in[i]);
else in[i - 1] += (in[i] - out[i]), res += 1LL * (val[i] - val[i - 1]) * (in[i] - out[i]);
}else ed.push_back({val[i] - val[i - 1], {i, i - 1}});
}
// cout << res << '\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 0;
return res;
}
//int main()
//{
// return 0;
//}
