#include<bits/stdc++.h>
#include "railroad.h"
const int inf=2e9;
#define ll long long
using namespace std;
vector<int>nex;
int findt(int node)
{
if (nex[node]!=-1)
return nex[node]=findt(nex[node]);
return node;
}
bool onion(int x,int y)
{
x=findt(x);
y=findt(y);
if (x==y)
return 0;
nex[y]=x;
return 1;
}
ll plan_roller_coaster(vector<int>s,vector<int>t)
{
s.push_back(inf);
t.push_back(1);
int n=s.size();
vector<int>aux=s;
aux.insert(aux.end(),t.begin(),t.end());
sort(aux.begin(),aux.end());
aux.erase(unique(aux.begin(),aux.end()),aux.end());
int m=aux.size();
nex.resize(m,-1);
vector<int>b(m--);
int i;
for(i=0;i<n;i++){
int st=lower_bound(aux.begin(),aux.end(),s[i])-aux.begin();
int dr=lower_bound(aux.begin(),aux.end(),t[i])-aux.begin();
onion(st,dr);
++b[st];
--b[dr];
}
for(i=0;i<m;i++)
b[i+1]+=b[i];
vector<pair<int,int>>pi;
ll ans=0;
for(i=0;i<m;i++){
ll sum=aux[i+1]-aux[i];
if (b[i]){
onion(i,i+1);
if (b[i]>0)
ans=ans+b[i]*sum;
}
else
pi.push_back({sum,i});
}
sort(pi.begin(),pi.end());
for(auto it:pi)
if (onion(it.second,it.second+1))
ans+=it.first;
return ans;
}
