#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
const ll INF = 1e18;
int n,m;
vec s,t;
ll bitdp[1 << 16][16];
int ind[400005],oud[400005],mx;
int c[400005],p[400005];
vec rev;
vector <int> v[400005];
vector <pair<int,pi>> edge;
int Find(int x) {return (x == p[x] ? x : p[x] = Find(p[x]));}
ll dist(int x,int y) {
return max(0,t[x]-s[y]);
}
void merge(int x,int y) {
x = Find(x), y = Find(y);
if(x == y) return;
p[y] = x;
}
void dfs(int x,int co) {
if(p[x] != -1) return;
p[x] = co;
for(int i : v[x]) dfs(i,co);
}
ll plan_roller_coaster(vec S,vec T) {
s = S, t = T;
n = s.size();
for(int i = 0;i < n;i++) {
rev.push_back(s[i]);
rev.push_back(t[i]);
}
sort(rev.begin(),rev.end());
rev.erase(unique(rev.begin(),rev.end()),rev.end());
m = rev.size();
for(int i = 0;i < n;i++) {
s[i] = lower_bound(rev.begin(),rev.end(),s[i])-rev.begin();
t[i] = lower_bound(rev.begin(),rev.end(),t[i])-rev.begin();
oud[s[i]]++, ind[t[i]]++;
v[s[i]].push_back(t[i]);
}
ll ans = 0;
for(int i = 0;i < m-1;i++) {
int tmp = ind[i]-oud[i];
if(!i) tmp++;
if(ind[i] > oud[i]+(i?0:-1)) v[i].push_back(i+1);
if(ind[i] < oud[i]+(i?0:-1)) ans -= 1LL*(rev[i+1]-rev[i])*tmp, v[i+1].push_back(i);
oud[i] += tmp;
ind[i+1] += tmp;
edge.push_back({rev[i+1]-rev[i],{i,i+1}});
}
sort(edge.begin(),edge.end());
memset(p,-1,sizeof(p));
for(int i = 0;i < m;i++) dfs(i,i);
for(auto i : edge) {
int x = i.y.x, y = i.y.y;
int cost = i.x;
if(Find(x) == Find(y)) continue;
//cout << x << ' ' << y << " : " << cost << '\n';
merge(x,y);
ans += cost;
}
return ans;
}
