/*******************
* what the sigma *
********************/
#pragma GCC optimize("O3","unroll-loops")
#include <iostream>
#include <vector>
#include <map>
#include <chrono>
#include <set>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
bool enabledb=0;
#define DB(CODE) cout<<'\t'<<CODE<<endl;
#define SP <<' '<<
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define tll tuple<ll,ll,ll>
#define sz(x) ((int)x.size())
#define pb push_back
const ll mod = 998244353,maxn=200005,root=3;
const ll INF=(ll)1e9+1004;
// ve<int> t(maxn*4);
// int n;
// void add(int u,int l,int r,int idx,int v) {
// if (l==r) {t[u]+=v;return;}
// int mid=(l+r)>>1;
// if (mid+1<=idx) {
// add(u<<1|1,mid+1,r,idx,v);
// }
// if (mid>=idx) {
// add(u<<1,l,mid,idx,v);
// }
// t[u]=min(t[u<<1],t[u<<1|1]);
// }
// void add(int idx,int v) {
// add(1,0,n,idx,v);
// }
// int qry(int u,int l,int r,int tl,int tr) {
// if (l>tr||r<tl) return 1e9;
// if (l>=tl&&r<=tr) {
// return t[u];
// }
// int mid=(l+r)>>1;
// return min(qry(u<<1,l,mid,tl,tr),qry(u<<1|1,mid+1,r,tl,tr));
// }
// int qry(int l,int r){
// return qry(1,0,n,l,r);
// }
ve<pll> ed[maxn];
int pa[maxn];
int find(int u){
if (pa[u]==u) return u;
return pa[u]=find(pa[u]);
}
void unite(int u,int v) {
u=find(u),v=find(v);
if (u==v) return;
pa[v]=u;
}
// int main() {
// lgm;
// }
ll plan_roller_coaster(ve<int> s, ve<int> t) {
int n=sz(s);
if (n<=8) {
ve<pll> a(n);
for (int i=0;i<n;i++) {
a[i]={s[i],t[i]};
}
sort(be(a));
ll ans=1e18;
do {
ll asn=0;
for (int i=1;i<n;i++) {
asn+=max(0ll,a[i-1].s-a[i].f);
}
ans=min(ans,asn);
} while (next_permutation(be(a)));
return ans;
}
if (n<=16) {
ve<pll> a(n);
for (int i=0;i<n;i++) {
a[i]={s[i],t[i]};
}
sort(be(a));
ve<ve<ll>> dp((1<<n),ve<ll>(n,1e18));
for (int i=0;i<n;i++) {
dp[(1<<i)][i]=0;
}
for (int i=1;i<(1<<n);i++) {
for (int j=0;j<n;j++) {
if (i&(1<<j)) continue;
for (int k=0;k<n;k++) {
if (i&(1<<k)) {
dp[i|(1<<j)][j]=min(dp[i|(1<<j)][j],dp[i][k]+max(0ll,a[k].s-a[j].f));
}
}
}
}
ll ans=1e18;
for (int i=0;i<n;i++) {
ans=min(ans,dp[(1<<n)-1][i]);
}
return ans;
}
s.insert(s.begin(),-1);
t.insert(t.begin(),-1);
ve<pll> a(n+1);
ve<pll> b;
for (int i=1;i<=n;i++) {
a[i]={s[i],t[i]};
b.pb({a[i].f,i});
b.pb({a[i].s,-i});
}
b.pb({INF,n+1});
b.pb({1,-n-1});
sort(be(b));
for (int i=1;i<=n+1;i++) {
pa[i]=i;
}
pa[0]=0;
stack<int> st[2];
ll ans=0,prev=0;
for (auto [x,i]:b) {
bool t=(i<0);
i=abs(i);
ans+=1ll*sz(st[0])*(x-prev);
prev=x;
if (!st[!t].empty()) {
unite(i,st[!t].top());
st[!t].pop();
} else {
if (!st[t].empty()) {
unite(i,st[t].top());
}
st[t].push(i);
}
}
ve<array<ll, 3>>edge;
for(int i = 0; i + 1 < sz(b); i++){
edge.pb({b[i + 1].f - b[i].f, abs(b[i].s), abs(b[i + 1].s)});
}
sort(be(edge));
for(auto& [w, u, v] : edge){
if(find(u)!=find(v)){
unite(u,v);
ans += w;
}
}
return ans;
}
