#include "railroad.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
using namespace std;
const int N = 4e5 + 5;
const int inf = 1e18;
int par[N];
int dsu(int a){return par[a] = (a == par[a] ? a : dsu(par[a]));}
long long plan_roller_coaster(std::vector<int32_t> s, std::vector<int32_t> t) {
int n = s.size();
map <int, int> mp;
iota(par, par + N, 0ll);
vector <int> comp;
for (int i = 0; i < n; i++) comp.emb(s[i]), comp.emb(t[i]);
comp.emb(1);
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
int m = comp.size();
for (int i = 0; i < n; i++) {
int ss = lower_bound(all(comp), s[i]) - comp.begin();
int tt = lower_bound(all(comp), t[i]) - comp.begin();
mp[ss]++;
mp[tt]--;
par[dsu(ss)] = dsu(tt);
}
par[dsu(0)] = dsu(comp.size());
mp[0]--;
mp[inf]++;
comp.emb(inf);
int cur = 0;
int ans = 0;
vector <tiii> edge;
for (auto [x, y] : mp) {
cur += y;
if (cur > 0) ans += cur * (comp[x + 1] - comp[x]), par[dsu(x)] = dsu(x + 1);
if (cur == 0 && x != inf) edge.emb(comp[x + 1] - comp[x], x, x + 1);
if (cur < 0) par[dsu(x)] = dsu(x + 1);
}
sort(all(edge));
for (auto [w, u, v] : edge) {
if (dsu(u) != dsu(v)) {
par[dsu(u)] = dsu(v);
ans += w;
}
}
return ans;
}
