#include <bits/stdc++.h>
using namespace std;
map<int, int> par;
int find(int u) {
if (par.count(u) > 0) {
return par[u] = find(par[u]);
} else {
return u;
}
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if (u != v) {
par[u] = v;
return true;
}
return false;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
s.push_back(INT_MAX), t.push_back(1);
int n = s.size();
map<int, int> events;
for (int i = 0; i < n; ++i) {
unite(s[i], t[i]);
++events[s[i]];
--events[t[i]];
}
long long ans = 0;
int prv = 1, balance = 0;
vector<array<int, 3>> edges;
for (auto [x, d] : events) {
if (balance != 0) {
ans += (long long) (x - prv) * max(0, balance);
unite(prv, x);
}
edges.push_back({x - prv, prv, x});
balance += d;
prv = x;
}
sort(edges.begin(), edges.end());
for (auto [w, u, v] : edges) {
if (unite(u, v)) {
ans += w;
}
}
return ans;
}
