#include "railroad.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
void dfs(int here, const vector<vector<int>> &graph, vector<int> &palette,
int color) {
if (palette[here]) return;
palette[here] = color;
for (auto there : graph[here]) dfs(there, graph, palette, color);
}
class disjointSet {
public:
vector<int> p;
disjointSet() = default;
explicit disjointSet(int N) {
p.clear();
p.resize(N);
for (int i = 0; i < N; i++) p[i] = i;
}
int find(int u) { return p[u] = (p[u] == u ? u : find(p[u])); }
void mer(int u, int v) { p[find(v)] = find(u); }
bool sset(int u, int v) { return find(u) == find(v); }
};
i64 plan_roller_coaster(vector<int> s, vector<int> t) {
const int N = (int)s.size();
vector<i64> X;
copy(iterall(s), back_inserter(X));
copy(iterall(t), back_inserter(X));
sort(iterall(X));
X.erase(unique(iterall(X)), X.end());
const int M = (int)X.size();
vector<i64> deg(M);
vector<vector<int>> pregraph(M);
for (int i = 0; i < N; i++) {
auto S = lower_bound(iterall(X), s[i]) - X.begin();
auto T = lower_bound(iterall(X), t[i]) - X.begin();
pregraph[S].emplace_back(T);
deg[S]++;
deg[T]--;
}
i64 ret = 0;
for (int i = 0; i < M - 1; i++) {
i64 targetDeg = (i ? 0 : 1);
i64 diff = targetDeg - deg[i];
if (deg[i] < targetDeg) {
pregraph[i].emplace_back(i + 1);
} else if (deg[i] > targetDeg) {
pregraph[i + 1].emplace_back(i);
ret -= (diff * (X[i + 1] - X[i]));
}
deg[i] += diff;
deg[i + 1] -= diff;
}
int color = 1;
vector<int> palette(M);
for (int i = 0; i < M; i++) {
if (palette[i]) continue;
dfs(i, pregraph, palette, color++);
}
priority_queue<tli, vector<tli>, greater<>> pq;
for (int i = 0; i < M - 1; i++) {
if (palette[i] == palette[i + 1]) continue;
pq.emplace(X[i + 1] - X[i], palette[i], palette[i + 1]);
}
auto dS = disjointSet(color);
while (!pq.empty()) {
auto [w, u, v] = pq.top();
pq.pop();
if (!dS.sset(u, v)) dS.mer(u, v), ret += w;
}
return ret;
}
