#include "railroad.h"
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int inf = 1e9+5;
int id = 0;
vector<set<int>>adj; vi vis, cc;
void dfs(int node){
vis[node] = 1; cc[node] = id;
for(auto u : adj[node]){
if(vis[u])continue;
dfs(u);
}
}
struct DSU{
vi par, sz;
DSU(int n){
par.resize(n); sz.resize(n); f0r(i,n)par[i]=i,sz[i]=1;
}
int find(int x){
if(x == par[x])return x; return par[x] = find(par[x]);
}
void unite(int a, int b){
a = find(a); b = find(b); if(a==b)return;
if(sz[a] < sz[b])swap(a,b);
sz[a] += sz[b];
par[b] = a;
}
};
long long plan_roller_coaster(std::vector<signed> s, std::vector<signed> t) {
int ans = 0;
s.pb(inf); t.pb(1); int n = s.size(); vpii w(n); f0r(i,n)w[i].first=s[i],w[i].second=t[i]; map<int,int> cmp; set<int>gg;
for(auto [a,b] : w)gg.insert(a),gg.insert(b); vi g; for(auto u : gg)g.pb(u); f0r(i,g.size())cmp[g[i]]=i;
int m = g.size(); adj.resize(m); vi d(m); for(auto [x,y] : w){
int a = cmp[x], b = cmp[y]; adj[a].insert(b); int dif = 1; if(a > b)swap(a,b),dif=-1;
d[a]+=dif; d[b]-=dif;
}
int cur = 0; vi cr(m-1); f0r(i,m-1){
cur += d[i]; cr[i] = cur; if(cr[i] > 0){
ans += (g[i+1] - g[i]) * cr[i]; adj[i+1].insert(i);
}
if(cr[i] < 0){
adj[i].insert(i+1);
}
}
vis.resize(m); cc.resize(m);
f0r(i,m)if(!vis[i]){
dfs(i);
id++;
}
int k = id; vector<pair<int,pii>>edges; DSU D = DSU(k);
f0r(i,m-1)if(cc[i] != cc[i+1]){
edges.pb(mp(g[i+1] - g[i], mp(cc[i], cc[i+1])));
}
sort(edges.begin(),edges.end()); f0r(i,edges.size()){
int w = edges[i].first; int a = edges[i].second.first, b = edges[i].second.second;
if(D.find(a)==D.find(b))continue;
ans+=w; D.unite(a,b);
}
return ans;
}
