#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSU {
int n;
vector<int> sz, par;
DSU(int _n) {
n = _n;
sz = vector<int>(n, 1);
par = vector<int>(n);
for (int i = 0; i < n; i++) par[i] = i;
}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
bool join(int x, int y) {
x = find(x), y = find(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
par[y] = x;
return 1;
}
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
s.push_back(1e9), t.push_back(1);
int n = (int) s.size();
DSU dsu(n);
vector<array<int, 3>> p(2*n), e(2*n-1);
for (int i = 0; i < n; i++) {
p[2*i] = {s[i], 1, i};
p[2*i+1] = {t[i], -1, i};
}
sort(p.begin(), p.end());
ll ans = 0;
ll d = 0;
for (int i = 0; i < 2*n-1; i++) {
d += p[i][1];
ans += max(0ll, d)*(p[i+1][0]-p[i][0]);
e[i] = {p[i+1][0]-p[i][0], p[i][2], p[i+1][2]};
if (d || p[i][0] == p[i+1][0]) dsu.join(p[i][2], p[i+1][2]);
}
sort(e.begin(), e.end());
for (int i = 0; i < 2*n-1; i++) ans += dsu.join(e[i][1], e[i][2])*e[i][0];
return ans;
}
