#include "railroad.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
vector<int> bo;
void init(int x){
bo.resize(x);
iota(bo.begin(),bo.end(),0);
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
int merge(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return 0;
}
bo[x]=y;
return 1;
}
}dsu;
const int inf=1e9;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n=s.size();
vector<pair<int,int> > a(n+1),b(n+1);
for(int i=0;i<n;i++){
a[i]={s[i],i};
b[i]={t[i],i};
}
a[n]={inf,n};
b[n]={1,n};
n++;
dsu.init(n);
sort(a.begin(),a.end());
sort(b.begin(),b.end());
long long sum=0,ax=0;
for(int i=0;i<n;i++){
dsu.merge(a[i].sc,b[i].sc);
sum+=abs(a[i].fs-b[i].fs);
ax+=a[i].fs;
ax-=b[i].fs;
}
p_q<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
for(int i=0;i+1<n;i++){
pq.push({2*max(0,min(a[i+1].fs,b[i+1].fs)-max(a[i].fs,b[i].fs)),i});
}
while(pq.size()){
auto h=pq.top();
pq.pop();
sum+=dsu.merge(a[h.sc].sc,a[h.sc+1].sc)*h.fs;
}
return (sum-ax)/2;
}
