#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
int par[400010], deg[400010], chk[400010];
int get(int i) {
if (par[i]==i) return i;
else return par[i]=get(par[i]);
}
vim V[400010], cp;
int N, M, tp;
ll ans;
void dfs(int now, int num) {
chk[now]=num;
for (int i:V[now]) if (!chk[i]) dfs(i, num);
}
ll plan_roller_coaster(vim s, vim t) {
N=s.size();
//coordinate compression
for (int i:s) cp.push_back(i);
for (int i:t) cp.push_back(i);
sort(all(cp)); cp.erase(unique(all(cp)), cp.end()); M=cp.size();
vim S, T;
S.push_back(0); T.push_back(0);
for (int i:s) {
int lb=lower_bound(all(cp), i)-cp.begin();
S.push_back(lb+1);
deg[lb+1]++;
}
for (int i:t) {
int lb=lower_bound(all(cp), i)-cp.begin();
T.push_back(lb+1);
deg[lb+1]--;
}
//generate edges
for (int i=1; i<=N; i++) V[S[i]].push_back(T[i]);
for (int i=1; i<M; i++) {
int req=(i==1?1:0);
int now=req-deg[i];
if (now>0) {
deg[i]+=now;
deg[i+1]-=now;
V[i].push_back(i+1);
}
else if (now<0) {
deg[i]+=now;
deg[i+1]-=now;
V[i+1].push_back(i);
ans+=(ll)abs(now)*(cp[i]-cp[i-1]);
}
}
//mst
for (int i=1; i<M; i++) if (!chk[i]) dfs(i, ++tp);
for (int i=1; i<=tp; i++) par[i]=i;
vector<pii> e;
for (int i=1; i<M; i++) if (chk[i]!=chk[i+1]) e.push_back({cp[i]-cp[i-1], i});
sort(all(e));
for (pii pi:e) {
int x1=get(chk[pi.se]), x2=get(chk[pi.se+1]);
if (x1!=x2) {
ans+=(ll)pi.fi;
par[x2]=x1;
}
}
return ans;
}
