#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct DSU{
vector<int> lab;
void init(int n){
lab.assign(n+1, -1);
}
int find_set(int u){
return lab[u]<0?u:lab[u]=find_set(lab[u]);
}
bool union_sets(int u, int v){
u=find_set(u); v=find_set(v);
if (u!=v){
if (lab[u]>lab[v]) swap(u, v);
lab[u]+=lab[v];
lab[v]=u;
return 1;
}
return 0;
}
} dsu;
const int N=4e5+10;
int d[N];
long long plan_roller_coaster(vector<int32_t> s, vector<int32_t> t) {
vector<int> vals={-1};
for (auto i:s) vals.push_back(i);
for (auto i:t) vals.push_back(i);
sort(vals.begin(), vals.end()); vals.resize(unique(vals.begin(), vals.end())-vals.begin());
int m=(int)vals.size()-1;
dsu.init(m);
s.push_back(1e9); t.push_back(1);
for (auto &i:s) i=lower_bound(vals.begin(), vals.end(), i)-vals.begin();
for (auto &i:t) i=lower_bound(vals.begin(), vals.end(), i)-vals.begin();
int n=s.size();
for (int i=0; i<n; ++i){
++d[s[i]];
--d[t[i]];
dsu.union_sets(s[i], t[i]);
}
partial_sum(d, d+N, d);
int ans=0;
vector<pair<int, pair<int, int>>> v;
for (int i=1; i<m; ++i){
if (d[i]) dsu.union_sets(i, i+1);
if (d[i]>0) ans+=(vals[i+1]-vals[i])*d[i];
v.push_back({vals[i+1]-vals[i], {i, i+1}});
}
sort(v.begin(), v.end());
for (auto &i:v) if (dsu.union_sets(i.second.first, i.second.second)) ans+=i.first;
return ans;
}
