#include "railroad.h"
#include <algorithm>
using namespace std;
int x[400004], xn;
int a[400004];
int p[400004];
pair<int, pair<int, int> > d[400004];
int dn;
int f(int x) {
return x == p[x] ? x : p[x] = f(p[x]);
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
long long r = 0;
int n = (int) s.size();
int i;
for (i = 0; i < n; i++) {
x[xn++] = s[i];
x[xn++] = t[i];
}
sort(x, x + xn);
xn = unique(x, x + xn) - x;
for (i = 0; i <= xn; i++) p[i] = i;
for (i = 0; i < n; i++) {
s[i] = lower_bound(x, x + xn, s[i]) - x;
t[i] = lower_bound(x, x + xn, t[i]) - x;
a[s[i]]++, a[t[i]]--;
p[f(s[i])] = f(t[i]);
}
for (i = 0; i < xn; i++) {
a[i + 1] += a[i];
if (a[i] != 1) {
p[f(i)] = f(i + 1);
if (a[i] > 1) r += (a[i] - 1ll) * (x[i + 1] - x[i]);
}
else {
d[dn].first = x[i + 1] - x[i];
d[dn].second.first = i;
d[dn].second.second = i + 1;
dn++;
}
}
sort(d, d + dn);
for (i = 0; i < dn; i++) if (f(d[i].second.first) != f(d[i].second.second)) {
r += d[i].first;
p[f(d[i].second.first)] = d[i].second.second;
}
return r;
}
