#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
const int INF = 1e9+1;
struct DSU {
vec<int> par;
vec<int> sz;
DSU(int n) {
par = vec<int>(n);
sz = vec<int>(n, 1);
iota(par.begin(), par.end(), 0);
}
int root(int u) {
if(par[u] == u) return u;
par[u] = root(par[u]);
return par[u];
}
bool join(int u, int v) {
u = root(u);
v = root(v);
if(u == v) return false;
if(sz[v] > sz[u]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return true;
}
};
int plan_roller_coaster(vec<int32_t> s, vec<int32_t> t) {
int32_t n = (int32_t) s.size();
map<int, int> bal_dif;
for(int i = 0; i<n; i++) {
bal_dif[s[i]]++;
bal_dif[t[i]]--;
}
bal_dif[1]--;
bal_dif[INF]++;
int bal = 0;
int prev = 0;
int ans = 0;
set<pair<int, pair<int, int>>> edges;
DSU dsu(bal_dif.size()+5);
map<int, int> eps_ind;
int cnt = 1;
eps_ind[0] = 0;
for(auto [i, b_add] : bal_dif) {
eps_ind[i] = cnt;
if(bal > 0) {
ans += bal * (i-prev);
dsu.join(eps_ind[i], eps_ind[prev]);
}
else if(bal < 0) {
dsu.join(eps_ind[i], eps_ind[prev]);
}
else if (prev != 0) {
edges.insert({i-prev, {eps_ind[prev], eps_ind[i]}});
}
bal += b_add;
prev = i;
cnt++;
}
dsu.join(eps_ind[1], eps_ind[INF]);
for(int i = 0; i<n; i++) {
dsu.join(eps_ind[s[i]], eps_ind[t[i]]);
}
//cerr << ans << '\n';
while(edges.size() > 0) {
auto it = edges.begin();
auto [w, eps] = *it;
edges.erase(it);
if(dsu.join(eps.first, eps.second)) {
ans += w;
}
}
return ans;
}
