#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
s.push_back(1e9 + 228);
t.push_back(0);
vector<int> x(s.begin(), s.end());
x.insert(x.end(), t.begin(), t.end());
sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
const int n = s.size(), m = x.size();
vector<int> b(m), p(m);
iota(p.begin(), p.end(), 0);
auto get = [&](int x) {
while (x != p[x]) x = p[x] = p[p[x]];
return x;
};
auto unite = [&](int a, int b) {
a = get(a), b = get(b);
if (a == b) return false;
p[b] = a;
return true;
};
for (int i = 0; i < n; ++i) {
int S = lower_bound(x.begin(), x.end(), s[i]) - x.begin();
int T = lower_bound(x.begin(), x.end(), t[i]) - x.begin();
++b[S];
--b[T];
unite(S, T);
}
vector<array<int, 3>> edges;
long long ans = 0;
int balance = 0;
for (int i = 0; i < m; ++i) {
if (balance != 0) {
ans += 1LL * (x[i] - x[i - 1]) * max(0, balance);
unite(i, i - 1);
}
balance += b[i];
if (i > 0) {
edges.push_back({x[i] - x[i - 1], i, i - 1});
}
}
sort(edges.begin(), edges.end());
for (auto [w, u, v]: edges) {
if (unite(u, v)) {
ans += w;
}
}
return ans;
}
