#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const int N = 400100;
int n, m, val[N], fa[N];
map<int, int> coords;
vector<int> good;
vector<pair<int, pair<int, int>>> edges;
int find(int v){return v==fa[v]?v:fa[v]=find(fa[v]);}
void unite(int u, int v){
u = find(u), v = find(v);
if(u==v) return;
fa[u] = v;
}
ll plan_roller_coaster(vector<int> _s, vector<int> _t){
_s.push_back(1e9);
_t.push_back(1);
n = _s.size();
for(int i = 0; i<n; ++i)
good.push_back(_s[i]), good.push_back(_t[i]);
sort(good.begin(), good.end());
good.erase(unique(good.begin(), good.end()), good.end());
m = good.size();
iota(fa, fa+N, 0);
for(int i = 0; i<m; ++i)
coords[good[i]] = i;
for(int i = 0; i<n; ++i)
++val[coords[_s[i]]], --val[coords[_t[i]]], unite(coords[_s[i]], coords[_t[i]]);
int curcnt = 0; ll ans = 0;
for(int i = 0; i<m-1; ++i){
curcnt += val[i];
if(curcnt>0) ans += 1ll*curcnt*(good[i+1]-good[i]), unite(i, i+1);
else if(curcnt<0) unite(i, i+1);
val[i] -= curcnt, val[i+1] += curcnt;
curcnt = 0;
}
for(int i = 0; i<m-1; ++i)
edges.push_back({good[i+1]-good[i], {i, i+1}});
sort(edges.begin(), edges.end());
for(auto e : edges)
if(find(e.s.f)!=find(e.s.s))
ans += e.f, unite(e.s.f, e.s.s);
return ans;
}
