#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
const ll LINF = 1e18;
int n;
vector<int>s, t;
namespace sub1{
ll solve(){
vector<int>p(n);
iota(p.begin(), p.end(), 0);
ll ans = LINF;
do{
ll sum = 0;
for(int i = 0; i + 1 < n; i++){
if(t[p[i]] > s[p[i + 1]]){
sum += t[p[i]] - s[p[i + 1]];
}
}
minimize(ans, sum);
} while(next_permutation(p.begin(), p.end()));
return ans;
}
}
namespace sub2{
ll solve(){
vector<vector<ll>>dp(1 << n, vector<ll>(n, LINF));
for(int i = 0; i < n; i++){
dp[1 << i][i] = 0;
}
for(int mask = 0; mask < (1 << n); mask++){
for(int i = 0; i < n; i++){
if(mask >> i & 1){
for(int j = 0; j < n; j++){
if((mask >> j & 1) == 0){
minimize(dp[mask | (1 << j)][j], dp[mask][i] + max(0, t[i] - s[j]));
}
}
}
}
}
return *min_element(dp.back().begin(), dp.back().end());
}
}
namespace sub34{
const int INF = 1e9 + 36;
const int lim = 2e5 + 5;
int lab[lim];
vector<int>stk[2];
int find_set(int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
}
bool merge(int i, int j){
if((i = find_set(i)) != (j = find_set(j))){
lab[j] = i;
return true;
}
return false;
}
ll solve(){
s.insert(s.begin(), -1);
s.push_back(INF);
t.insert(t.begin(), -1);
t.push_back(1);
vector<pair<int, int>>point;
for(int i = ++n; i > 0; i--){
point.push_back(make_pair(s[i], i));
point.push_back(make_pair(t[i], -i));
}
sort(point.begin(), point.end());
iota(lab + 1, lab + n + 1, 1);
int last = 0;
ll ans = 0;
for(auto& [p, i] : point){
bool nega = i < 0;
i = abs(i);
ans += ll(stk[0].size()) * (p - last);
last = p;
if(!stk[!nega].empty()){
merge(i, stk[!nega].back());
stk[!nega].pop_back();
}
else{
if(!stk[nega].empty()){
merge(i, stk[nega].back());
}
stk[nega].push_back(i);
}
}
vector<array<int, 3>>edge;
for(int i = 0; i + 1 < point.size(); i++){
edge.push_back({point[i + 1].first - point[i].first, abs(point[i].second), abs(point[i + 1].second)});
}
sort(edge.begin(), edge.end());
for(auto& [w, u, v] : edge){
if(merge(u, v)){
ans += w;
}
}
return ans;
}
}
ll plan_roller_coaster(vector<int>_s, vector<int>_t){
swap(s, _s);
swap(t, _t);
if((n = s.size()) <= 8){
return sub1::solve();
}
if(n <= 16){
return sub2::solve();
}
return sub34::solve();
}
