#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
map<int,int> m;
const int maxn = 4e5 + 10;
vector<int> grafo[maxn];
struct DSU{
int pai[maxn];
void init(int n){ for(int i=0; i<maxn; i++) pai[i] = i; }
int find(int x){ return pai[x] == x ? x : pai[x] = find(pai[x]); }
bool join(int a, int b){
a = find(a), b = find(b);
if(a == b) return 0;
pai[b] = a; return 1;
}
}dsu;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int)s.size() + 1;
s.push_back(1e9);
t.push_back(1);
vector<int> v;
for(int x : s) v.push_back(x);
for(int x : t) v.push_back(x);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int tt = 0;
for(int x : v) m[x] = tt++;
vector<int> sum(tt+1, 0);
dsu.init(tt);
for(int i=0; i<n; i++){
int u = m[s[i]], v = m[t[i]];
if(u == v) continue;
dsu.join(u, v);
++sum[u], --sum[v];
}
ll ans = 0;
for(int i=0; i<tt; i++){
if(i) sum[i] += sum[i-1];
if(sum[i] != 0){
dsu.join(i, i+1);
ans += 1LL * max(sum[i], 0) * (v[i+1] - v[i]);
}
}
vector<pii> q;
for(int i=0; i+1<tt; i++) if(dsu.find(i) != dsu.find(i+1)) q.push_back({v[i+1] - v[i], i});
sort(q.begin(), q.end());
for(auto [w, i] : q) if(dsu.join(i, i+1)) ans += w;
return ans;
}
