#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
vector<int> dsu, ord;
int id(int a){
return lower_bound(ord.begin(), ord.end(), a)-ord.begin();
}
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
bool merge(int a, int b){
a=fp(a), b=fp(b);
if (a==b)return 0;
dsu[a]=b;
return 1;
}
long long plan_roller_coaster(vector<int> s, vector<int> t){
ord.resize(2, 1);
ord[1]=1000000005;
for (int i=0; i<s.size(); ++i)ord.pb(s[i]), ord.pb(t[i]);
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
vector<int> psum(ord.size(), 0);
--psum[0], ++psum[ord.size()-1];
dsu.resize(ord.size(), -1);
merge(0, ord.size()-1);
for (int i=0; i<s.size(); ++i)++psum[id(s[i])], --psum[id(t[i])], merge(id(s[i]), id(t[i]));
vector<pair<int, pii> > edges;
long long ans=0;
for (int i=1; i<s.size(); ++i){
if (i)psum[i]+=psum[i-1];
if (psum[i-1])merge(i, i-1);
else edges.pb(mp(ord[i]-ord[i-1], mp(i, i-1)));
ans+=max(0ll, 1ll*psum[i-1]*(ord[i]-ord[i-1]));
}
sort(edges.begin(), edges.end());
for (auto c:edges)if (merge(c.se.fi, c.se.se))ans+=c.fi;
return ans;
}
