#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define X first
#define Y second
const int N = 4e5 + 5;
typedef pair<int,int> ii;
typedef pair<int,ii> ed;
int p[N];
int s[N];
int init(int n) {
iota(p,p + n,0);
fill(s,s + n,1);
return 1;
}
int lead(int x) {
return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y) {
x = lead(x);
y = lead(y);
if (x == y) return 0;
if (s[x] < s[y])
swap(x,y);
p[y] = x;
s[x] += s[y];
return 1;
}
int f[N];
ll plan_roller_coaster(vector<int> s,vector<int> t) {
s.pb(1e9);
t.pb(1);
int n = s.size();
vector<int> val;
for(int i = 0 ; i < n ; ++i) {
val.pb(s[i]);
val.pb(t[i]);
}
sort(all(val));
val.erase(unique(all(val)),val.end());
init(sz(val));
for(int i = 0 ; i < n ; ++i) {
int l = lower_bound(all(val),s[i]) - val.begin();
int r = lower_bound(all(val),t[i]) - val.begin();
f[l]++;
f[r]--;
join(l,r);
}
ll ans = 0;
ll Sum = 0;
vector<ed> E;
for(int i = 1 ; i < sz(val) ; ++i) {
Sum += f[i - 1];
if (Sum == 0) E.pb(val[i] - val[i - 1],ii(i - 1,i));
else {
join(i - 1,i);
if (Sum > 0)
ans += Sum * (val[i] - val[i - 1]);
}
}
sort(all(E));
for(ed e : E) {
int w = e.X;
int u = e.Y.X;
int v = e.Y.Y;
if (join(u,v))
ans += w;
}
return ans;
}
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
//
// cout << plan_roller_coaster({1,4,5,6},{7,3,8,6}) << endl;
//}
