#include <bits/stdc++.h>
using namespace std;
#include "railroad.h"
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
const int MX = 2e5 + 10;
int N;
vector<pair<int, pii>> vec;
struct dsu{
int p[MX];
void init(){
for(int i = 0; i < MX; i++) p[i] = i;
}
int f(int x){
if(x == p[x]) return x;
else return p[x] = f(p[x]);
}
bool Join(int u, int v){
int fu = f(u), fv = f(v);
if(fu == fv) return false;
p[fu] = fv;
return true;
}
} D;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
D.init();
N = s.size();
for(int i = 0; i < N; i++){
vec.push_back({s[i], {i, 1}});
vec.push_back({t[i], {i, -1}});
}
sort(vec.begin(), vec.end());
// Let the values be on a line
// We will calculate how many times a distance is traversed
// A distance is traversed optimally X times if there are X S values below this that do not have a T pair
// However because we cannot pair ith S with the ith T
// The T will be forced to pair with an S lower than this
int numS = 0; ll ans = 0;
int sz = vec.size();
for(int i = 0; i < sz - 1; i++){
if(vec[i].se.se == 1) numS++;
else numS--;
if(numS > 0) ans += 1ll * numS * (vec[i + 1].fi - vec[i].fi);
if(numS != 0) D.Join(vec[i].se.fi, vec[i + 1].se.fi);
}
// Force to pair with someone lower
numS = 0;
for(int i = 0; i < sz - 1; i++){
if(D.f(vec[i].se.fi) != D.f(vec[i + 1].se.fi)){
D.Join(vec[i].se.fi, vec[i + 1].se.fi);
ans += vec[i + 1].fi - vec[i].fi;
}
}
return ans;
}
