#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
struct DSU {
int n;
vector<int> par;
DSU(int n) : n(n), par(n, -1) {}
int find(int u) {
return par[u] == -1 ? u : par[u] = find(par[u]);
}
bool merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v)
return false;
par[v] = u;
return true;
}
};
ll plan_roller_coaster(vector<int> s, vector<int> t) {
int const n = (int) s.size();
vector<int> comp(begin(s), end(s));
comp.insert(end(comp), begin(t), end(t));
sort(begin(comp), end(comp));
comp.erase(unique(begin(comp), end(comp)), end(comp));
int const m = (int) comp.size();
vector<int> ps(m);
DSU dsu(m);
ll ans = 0;
for (int i = 0; i < n; i++) {
int l = lower_bound(begin(comp), end(comp), s[i]) - begin(comp);
int r = lower_bound(begin(comp), end(comp), t[i]) - begin(comp);
ps[l]++; ps[r]--;
dsu.merge(l, r);
}
ps[m - 1]++; ps[0]--;
partial_sum(begin(ps), end(ps), begin(ps));
vector<pair<int, int>> edges;
for (int i = 0; i + 1 < m; i++) {
if (ps[i] > 0)
ans += (ll) ps[i] * (comp[i + 1] - comp[i]);
if (ps[i] != 0)
dsu.merge(i, i + 1);
edges.emplace_back(comp[i + 1] - comp[i], i);
}
sort(begin(edges), end(edges));
for (auto & e : edges) {
if (dsu.merge(e.second, e.second + 1))
ans += e.first;
}
return ans;
}
