#include <bits/stdc++.h>
#include "railroad.h"
template <class T>
using Vec = std::vector<T>;
using ll = long long;
constexpr int MAX = 1000000000;
struct DSU {
Vec<int> par;
DSU(const int n): par(n, -1) { }
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
bool merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return false;
}
if (par[u] > par[v]) {
std::swap(u, v);
}
par[u] += par[v];
par[v] = u;
return true;
}
};
ll plan_roller_coaster(Vec<int> s, Vec<int> t) {
s.push_back(MAX);
t.push_back(1);
const int n = (int) s.size();
Vec<int> cmp;
cmp.reserve(2 * n);
std::copy(s.cbegin(), s.cend(), std::back_inserter(cmp));
std::copy(t.cbegin(), t.cend(), std::back_inserter(cmp));
std::sort(cmp.begin(), cmp.end());
cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
for (auto &x: s) {
x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
}
for (auto &x: t) {
x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
}
const int len = (int) cmp.size();
Vec<int> coeff(len);
for (const auto x: s) {
coeff[x] -= 1;
}
for (const auto x: t) {
coeff[x] += 1;
}
int current = 0;
DSU dsu(len);
ll ret = 0;
Vec<std::tuple<int, int, int>> edges;
for (int i = 0; i < len; ++i) {
current += coeff[i];
if (current < 0) {
ret += (ll) -current * (cmp[i + 1] - cmp[i]);
}
if (current != 0) {
dsu.merge(i, i + 1);
}
else if (i + 1 != len) {
edges.emplace_back(cmp[i + 1] - cmp[i], i, i + 1);
}
}
for (int i = 0; i < n; ++i) {
dsu.merge(s[i], t[i]);
}
std::sort(edges.begin(), edges.end());
for (const auto [c, u, v]: edges) {
if (dsu.merge(u, v)) {
ret += c;
}
}
return ret;
}
