#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N5=1e5;
const ll INF=1e18;
ll n;
vector<int> s, t;
ll ans[16][N5];
ll solve(ll i, ll k){
// cout<<i<<" "<<k<<endl;
if(k==((1ll<<n)-1)) return 0;
else if(ans[i][k]!=-1) return ans[i][k];
else{
ans[i][k]=INF;
for(ll j=0; j<n; j++){
if(k&(1ll<<j)) continue;
ans[i][k]=min(ans[i][k],solve(j,k|(1ll<<j))+max(0,t[i]-s[j]));
// cout<<i<<" ("<<t[i]<<") -> "<<j<<" ("<<s[j]<<"): "<<max(0,t[i]-s[j])<<endl;
}
return ans[i][k];
}
}
long long plan_roller_coaster(vector<int> s1, vector<int> t1) {
n=s1.size();
s=s1;
t=t1;
// for(ll i=0; i<n; i++){
// cout<<s1[i]<<" ";
// }
// cout<<endl;
// for(ll i=0; i<n; i++){
// cout<<t1[i]<<" ";
// }
// cout<<endl;
for(ll i=0; i<n; i++){
for(ll k=0; k<(1ll<<n); k++){
ans[i][k]=-1;
}
}
ll x=INF;
for(ll i=0; i<n; i++){
x=min(x,solve(i,(1ll<<i)));
// cout<<i<<" "<<x<<endl;
}
return x;
}
