#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 400010;
const int INF = 1e9+1;
int c;
vector<int> coord;
inline int pos(int x) { return upper_bound(coord.begin(), coord.end(), x) - coord.begin(); }
inline int &get(int i) { return coord[i-1]; }
int qs[N], par[N];
int root(int u) {
if (!par[u]) return u;
return par[u] = root(par[u]);
}
inline bool merge(int u, int v) {
u = root(u), v = root(v);
if (u == v) return false;
par[u] = v;
return true;
}
long long plan_roller_coaster(vector<int> s, vector<int> t)
{
// graph construction
int n = s.size();
coord.insert(coord.end(), s.begin(), s.end());
coord.insert(coord.end(), t.begin(), t.end());
coord.push_back(0);
coord.push_back(INF);
sort(coord.begin(), coord.end());
coord.resize(unique(coord.begin(), coord.end())-coord.begin());
c = coord.size();
qs[pos(0)] -= 1;
qs[pos(INF)] += 1;
for (int i = 0; i < n; ++i) {
int a = s[i], b = t[i], v = 1;
if (a > b) swap(a, b), v = -1;
a = pos(a), b = pos(b);
merge(a, b);
qs[a] += v;
qs[b] -= v;
}
// cost calculation and dsu
ll cost = 0;
vector<pii> E;
for (int i = 1; i <= c-1; ++i) {
qs[i] += qs[i-1];
ll dist = get(i+1)-get(i);
cost += max(qs[i]*dist, 0ll);
if (qs[i] != 0)
merge(i, i+1);
else
E.push_back(pii(dist, i));
}
sort(E.begin(), E.end());
for (auto e : E) {
if (merge(e.second, e.second+1))
cost += e.first;
}
return cost;
}
