#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define int long long
const int inf=1e18;
int dfs(int v, map<int, vector<int> >& adi, map<int, bool>& vis){
if(vis[v]) return 0;
vis[v]=true;
int cnt=1;
for(auto u: adi[v]){
cnt+=dfs(u, adi, vis);
}
return cnt;
}
bool connected(int n, int start, map<int, vector<int> >& adi){
map<int, bool> vis;
return dfs(start, adi, vis)==n;
}
int find_dp(int mask, int x, vector<vector<int> >& dp, vector<int32_t>& s, vector<int32_t>& t, int n){
if(dp[mask][x]!=inf) return dp[mask][x];
for(int i=0; i<n; i++){
if(i==x || (mask>>i)%2!=1) continue;
dp[mask][x]=min(dp[mask][x], find_dp(mask-(1<<x), i, dp, s, t, n)+max(0, t[x]-s[i]));
}
return dp[mask][x];
}
int plan_roller_coaster_bitmask(vector<int32_t> s, vector<int32_t> t){
int n=s.size();
int pow2=(1<<n);
vector<vector<int> > dp(pow2, vector<int> (n, inf));
for(int i=0; i<n; i++){
dp[(1<<i)][i]=0;
}
int ans=inf;
for(int i=0; i<n; i++){
ans=min(ans, find_dp(pow2-1, i, dp, s, t, n));
}
return ans;
}
int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t){
int n=s.size();
if(n<=16){
return plan_roller_coaster_bitmask(s, t);
}
map<int, vector<int> > adi;
vector<pair<int, int> > time;
for(int i=0; i<n; i++){
adi[s[i]].push_back(t[i]);
adi[t[i]].push_back(s[i]);
time.push_back({s[i], 1});
time.push_back({t[i], -1});
}
sort(time.begin(), time.end());
bool pos=true;
int sum=-1;
int dif=1;
for(int i=0; i<(int)time.size(); i++){
if(0<i && time[i-1].first!=time[i].first){
dif++;
}
sum+=time[i].second;
if(sum>0) pos=false;
if(sum<0 && i+1<(int)time.size()){
adi[time[i].first].push_back(time[i+1].first);
adi[time[i+1].first].push_back(time[i].first);
}
}
if(pos && connected(dif, s[0], adi)){
return 0;
}
return 1;
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int32_t> s(n);
vector<int32_t> t(n);
for(int i=0; i<n; i++){
cin >> s[i];
}
for(int i=0; i<n; i++){
cin >> t[i];
}
cout << plan_roller_coaster(s, t) << "\n";
}*/
