#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 404040
#define INF 1000000001
vector<int> all;
int deg[MAX];
int N;
int p[MAX];
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
void uni(int x, int y) {
x = find(x);
y = find(y);
p[x] = y;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
N = s.size();
for (auto v : s) all.push_back(v);
for (auto v : t) all.push_back(v);
all.push_back(INF);
all.push_back(0);
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
int X = all.size();
int i;
for (i = 0; i < X; i++) p[i] = i;
for (auto& v : s) v = lower_bound(all.begin(), all.end(), v) - all.begin();
for (auto& v : t) v = lower_bound(all.begin(), all.end(), v) - all.begin();
for (i = 0; i < N; i++) {
deg[s[i]]--;
deg[t[i]]++;
uni(s[i], t[i]);
}
deg[0]++;
deg[X - 1]--;
ll ans = 0;
for (i = 1; i < X; i++) {
if (deg[i - 1]) {
uni(i - 1, i);
if (deg[i - 1] < 0) ans += 1ll * -(ll)deg[i - 1] * ((ll)all[i] - all[i - 1]);
deg[i] += deg[i - 1];
}
}
vector<pii> vpi;
for (i = 1; i < X; i++) vpi.emplace_back(all[i] - all[i - 1], i);
sort(vpi.begin(), vpi.end());
for (auto& [c, v] : vpi) {
if (find(v - 1) != find(v)) {
uni(v - 1, v);
ans += c;
}
}
return ans;
}
