#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define eb(x...) emplace_back(x)
const int inf = 2e9;
using ll = int64_t;
using vi = vector<int>;
vi nxt;
int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
u = head(u); v = head(v);
if (u == v) return false;
nxt[v] = u; return true;
}
ll plan_roller_coaster(vi s, vi t) {
s.eb(inf); t.eb(1); int n = s.size();
vi p = s; p.insert(end(p), all(t));
sort(all(p)); p.erase(unique(all(p)), end(p));
int m = p.size(); nxt.resize(m, -1);
vi b(m--);
for(int i = 0; i < n; i++) {
int l = lb(all(p), s[i]) - begin(p), r = lb(all(p), t[i]) - begin(p);
unite(l, r); ++b[l]; --b[r];
}
for(int i = 0; i < m; i++) b[i + 1] += b[i];
vector<pair<int, int>> e; ll ans = 0;
for(int i = 0; i < m; i++) {
ll d = p[i + 1] - p[i];
if (b[i]) {
unite(i, i + 1);
if (b[i] > 0) ans += b[i] * d;
} else e.eb(d, i);
}
sort(all(e));
for (auto u : e) if (unite(u.second, u.second + 1)) ans += u.first;
return ans;
}
