#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 100003
#define pc(x) putchar_unlocked(x);
int n;
long long dep[18][(1<<16)+10];
vector<int>S,T;
long long dp(int now,int mask){
if(__builtin_popcount(mask)==n)return 0;
long long&ret=dep[now][mask];
if(ret!=-1)return ret;
ret=1e18;
for(int i=0;i<n;i++){
if(!(mask&(1<<i))){
long long cost=0;
if(T[now]>=S[i])cost=T[now]-S[i];
int nex=mask|(1<<i);
ret=min(ret,dp(i,nex)+cost);
}
}
return ret;
}
map<int,int>cnt;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
n=s.size();
S=s;
T=t;
if(n<=16){
T.pb(1);
reset(dep,-1);
return dp(n,0);
}
cnt[1]++;
for(int i:s){
cnt[i]--;
}
for(int i:t){
cnt[i]++;
}
int ada=0;
for(auto i:cnt){
if(i.s!=0){
if(!ada)ada=1;
else{
return 1;
}
}
}
return 0;
}
