#include "railroad.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;
typedef vector < int > vi;
ll n, m, k, ans, top, ata[N];
pair < int , ii > a[N], b[N];
ll atabul(ll x){return ata[x] = (ata[x]==x)?x:atabul(ata[x]);}
ll plan_roller_coaster(vi x, vi y) {
n = (int)x.size();
for(int i = 0; i < n; i++){
a[++m] = mp(x[i], mp(1, i));
a[++m] = mp(y[i], mp(-1, i));
}
a[++m] = mp(inf, mp(1, n));
a[++m] = mp(1, mp(-1, n));
for(int i = 0; i <= n; i++)ata[i] = i;
sort(a + 1, a + m + 1);
for(int i = 1; i <= m; i++){
top += a[i].nd.st;
// cout << i << " " << a[i].st << " " << top << endl;
ans += max(0ll, top)*(a[i + 1].st - a[i].st);
b[++k] = mp(a[i + 1].st - a[i].st, mp(a[i + 1].nd.nd, a[i].nd.nd));
if(top != 0){
int xx = atabul(a[i + 1].nd.nd);
int yy = atabul(a[i].nd.nd);
if(xx != yy)
ata[xx] = yy;
}
}
sort(b + 1, b + k + 1);
for(int i = 1; i <= k; i++){
int xx = atabul(b[i].nd.st);
int yy = atabul(b[i].nd.nd);
if(xx != yy){
ata[xx] = yy;
ans += b[i].st;
}
}
return ans;
}
