#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500000
int p[MAXN];
struct info {
int val;
int index;
int edgeType;
info(int a, int b, int c) {
val = a;
index = b;
edgeType = c;
}
bool operator <(const info& x) {
return val < x.val;
}
};
struct edge {
int s; int e; int cost;
edge(int start, int end, int c) {
s = start;
e = end;
cost = c;
}
bool operator <(const edge& x) {
return cost < x.cost;
}
};
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
bool merge(int x, int y) {
x = find(x); y = find(y);
p[x] = y;
return x != y;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
s.push_back(1e9+1);
t.push_back(1);
int n = (int) s.size();
vector<info> asd;
for (int i=0; i<n; i++) {
p[i] = i;
asd.emplace_back(s[i], i, 1);
asd.emplace_back(t[i], i, -1);
}
sort(asd.begin(), asd.end());
long long ans = 0;
vector<edge> edges;
for (int i=0, diff=0; i<2*n-1; i++) { // Looking at the next segment (i, i+1)
diff += asd[i].edgeType;
ans += 1LL * (asd[i+1].val - asd[i].val) * max(diff, 0);
edges.emplace_back(asd[i].index, asd[i+1].index, asd[i+1].val - asd[i].val);
if (diff != 0) {
merge(asd[i].index, asd[i+1].index);
}
}
sort(edges.begin(), edges.end());
for (int i=0; i<2*n; i++)
if (merge(edges[i].s, edges[i].e))
ans += 1LL * edges[i].cost;
return ans;
}
