#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const int INF = 1e9 + 9;
struct DSU {
vi p;
DSU(int n) : p(n, -1) {}
int find(int x) {
if (p[x] < 0) return x;
return p[x] = find(p[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (p[x] > p[y]) swap(x, y);
p[x] += p[y], p[y] = x;
return true;
}
};
ll plan_roller_coaster(vi s, vi t) {
s.pb(INF), t.pb(1);
int n = sz(s);
vi vals = s;
forn(i, n) vals.pb(t[i]);
sort(all(vals));
vals.erase(unique(all(vals)), end(vals));
auto pos = [&](int x) {
return int(lower_bound(all(vals), x) - begin(vals));
};
forn(i, n) s[i] = pos(s[i]), t[i] = pos(t[i]);
const int m = sz(vals);
DSU dsu(m);
forn(i, n) dsu.unite(s[i], t[i]);
vi delta(m);
forn(i, n) delta[s[i]]++, delta[t[i]]--;
vector<pair<ll, int>> edges;
ll pref = 0LL, ret = 0LL;
forn(i, m - 1) {
int dist = vals[i + 1] - vals[i];
pref += delta[i];
ret += max(0LL, pref) * dist;
if (pref != 0LL) dsu.unite(i, i + 1);
else edges.eb(dist, i);
}
sort(all(edges));
for (auto [w, i] : edges) {
if (dsu.unite(i, i + 1)) ret += w;
}
return ret;
}
