#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define int long long
const int inf=1e18;
int find_dp(int mask, int x, vector<vector<int> >& dp, vector<int32_t>& s, vector<int32_t>& t, int n){
/*for(int i=0; i<n; i++){
cout << (mask>>i)%2;
}
cout << " " << x << " =>" << dp[mask][x] << "\n" << flush;*/
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(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;
}
/*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";
}*/
