#include "railroad.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
vector <array<ll, 2>> A, B;
bool visited[200001];
ll nx[200001], G[200001], P[200001], f;
ll dsu(ll u) {
if (u == P[u]) return u;
else return P[u] = dsu(P[u]);
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
A.clear();
B.clear();
ll n = s.size()+1;
f = 0;
s.push_back((ll)1e9);
t.push_back(1);
for (int i=0; i<n; ++i) {
P[i] = i;
visited[i] = 0;
A.push_back({s[i], i});
B.push_back({t[i], i});
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
for (int i=0; i<n; ++i) {
f += max(0LL, B[i][0]-A[i][0]);
nx[B[i][1]] = A[i][1];
}
ll k = 0;
for (int i=0; i<n; ++i) {
if (visited[i]) continue;
ll u = i;
while (true) {
visited[u] = 1, G[u] = k;
u = nx[u];
if (u == i) break;
}
++k;
}
vector <array<ll, 3>> X;
vector <array<ll, 3>> W;
ll x = -1e18, l = 1e18;
for (int i=0; i<n; ++i) {
if (x == -1e18) {
x = max(A[i][0], B[i][0]), l = min(A[i][0], B[i][0]);
}
else if (x >= min(A[i][0], B[i][0])) {
x = max(A[i][0], B[i][0]);
if (i) {
ll a = dsu(G[A[i-1][1]]), b = dsu(G[A[i][1]]);
if (a != b) P[a] = b;
}
}
else {
X.push_back({l, max(A[i-1][0], B[i-1][0]), G[A[i-1][1]]});
x = max(A[i][0], B[i][0]), l = min(A[i][0], B[i][0]);
}
}
X.push_back({l, max(A.back()[0], B.back()[0]), G[A.back()[1]]});
for (int i=0; i+1<X.size(); ++i) {
W.push_back({X[i+1][0]-X[i][1], X[i][2], X[i+1][2]});
}
sort(W.begin(), W.end());
for (auto [w, u, v] : W) {
u = dsu(u), v = dsu(v);
if (u != v) {
f += w;
P[u] = v;
}
}
return f;
}
