// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "railroad.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 4e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;
int pr[maxn];
int fnd(int u){
return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
if( (a = fnd(a)) == (b = fnd(b)) )
return 0;
if(pr[a] > pr[b])
swap(a, b);
pr[a]+= pr[b];
pr[b] = a;
return 1;
}
ll plan_roller_coaster(vector<int> a, vector<int> b){
memset(pr, -1, sizeof pr);
int n = sz(a);
map<int, int> mp;
mp[0]++; // first of all
for(int x : a)
mp[x]--;
for(int x : b)
mp[x]++;
vector<int> tot;
for(int x : a)
tot.PB(x);
for(int x : b)
tot.PB(x);
tot.PB(0);
sort(tot.begin(), tot.end());
tot.resize( unique(tot.begin(), tot.end()) - tot.begin() );
auto comp = [&](int x){
return lower_bound(tot.begin(), tot.end(), x) - tot.begin();
};
int mrgs = 0;
for(int i = 0; i < n; i++){
mrgs+= mrg(comp(a[i]), comp(b[i]));
}
ll ans = 0;
int sum = 0, ID = 0;
for(auto it = mp.begin(); it != mp.end(); it++, ID++){
sum+= it->S;
if(sum < 0)
ans+= 1ll * abs(sum) * (tot[ID+1] - tot[ID]);
if(sum != 0)
mrgs+= mrg(ID, ID + 1);
}
vector< pair<int, pii> > eds;
for(int i = 0; i < sz(tot)-1; i++){
eds.PB({tot[i+1] - tot[i], {i, i+1}});
}
sort(eds.begin(), eds.end());
for(auto it : eds){
if(mrg(it.S.F, it.S.S))
ans+= it.F;
}
return ans;
}
