#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
int par[mxN], sz[mxN];
int find(int u) {
return (u == par[u] ? u : par[u] = find(par[u]));
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
if (sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
return true;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = s.size();
vector<pair<int, int>> all;
for (int i : s) all.push_back({i, 0});
for (int i : t) all.push_back({i, 1});
for (int i = 0; i < all.size(); i++) par[i] = i, sz[i] = 1;
int cur = 0;
long long ans = 0;
vector<tuple<int, int, int>> edges;
sort(all.begin(), all.end());
for (int i = 0; i < n; i++) {
int x = lower_bound(all.begin(), all.end(), pair<int, int> {s[i], 0}) - all.begin();
int y = lower_bound(all.begin(), all.end(), pair<int, int> {t[i], 1}) - all.begin();
merge(x, y);
}
for (int i = 0; i + 1 < all.size(); i++) {
auto [x, t] = all[i];
if (!t) cur++;
else cur--;
if (cur > 1) {
ans += 1LL * (cur - 1) * (all[i + 1].first - all[i].first);
merge(i, i + 1);
} else if (cur < 1) {
merge(i, i + 1);
}
edges.push_back({all[i + 1].first - all[i].first, i, i + 1});
}
sort(edges.begin(), edges.end());
for (auto [w, u, v] : edges) {
if (merge(u, v)) {
ans += w;
}
}
return ans;
}
