#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
struct dsu {
vector <int> par;
void init(int n){
par.assign(n, 0);
for (int i = 0; i < n; ++i) par[i] = i;
}
int findset(int u) {
if(par[u] == u) return u;
return par[u] = findset(par[u]);
}
bool mergeset(int u, int v) {
u = findset(u), v = findset(v);
if(u == v) return false;
par[v] = u; return true;
}
} pa;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = s.size();
#define int long long
vector<int> vals;
for (auto &v : s) vals.pb(v);
for (auto &v : t) vals.pb(v);
sort(begin(vals), end(vals));
vals.resize(unique(begin(vals), end(vals)) - begin(vals));
vector<int> can(vals.size() + 5, 0);
pa.init(vals.size() + 10);
for (int i = 0; i < n; ++i) {
s[i] = lower_bound(begin(vals), end(vals), s[i]) - begin(vals);
t[i] = lower_bound(begin(vals), end(vals), t[i]) - begin(vals);
can[s[i]]++;
can[t[i]]--;
pa.mergeset(s[i], t[i]);
}
int m = vals.size();
int cur = 1;
long long ans = 0;
vector<tuple<long long, int, int>> ts;
for (int i = m - 1; i > 0; --i) {
cur += can[i];
if(cur < 0) {
ans += 1ll * (vals[i - 1] - vals[i]) * cur;
pa.mergeset(i - 1, i);
} else if(cur > 0) pa.mergeset(i - 1, i);
else ts.emplace_back(vals[i] - vals[i - 1], i, i - 1);
}
sort(begin(ts), end(ts));
for (auto &_ : ts) {
int64_t w;
int u, v;
tie(w, u, v) = _;
if(pa.mergeset(u, v)) {
ans += w;
}
}
return ans;
}
