#include "railroad.h"
#include <cstring>
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
vector<int> gs,gt;
long long memo[16][65539];
int log2(int i){
int ans=0;
if (i>=256) ans+=8,i>>=8;
if (i>=16) ans+=4,i>>=4;
if (i>=4) ans+=2,i>>=2;
if (i>=2) ans+=1,i>>=1;
return ans;
}
int f(int i){
if (i<0) return 0;
return i;
}
long long tsp(int i,int bitmask){
if (bitmask==0) return 0;
else if (memo[i][bitmask]!=-1) return memo[i][bitmask];
long long ans=1123456789012345678;
int c_bitmask=bitmask,temp,log_temp;
while (c_bitmask!=0){
temp=c_bitmask&-c_bitmask;
c_bitmask-=temp;
log_temp=log2(temp);
ans=min(ans,tsp(log_temp,bitmask^temp)+ f(gt[i]-gs[log_temp]) );
}
return memo[i][bitmask]=ans;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
gs=s,gt=t;
int n = (int) s.size();
if (n>16){
priority_queue<ii> qs,qt;
for (int x=0;x<n;x++){
qs.push(ii (s[x],x));
qt.push(ii (t[x],x));
}
ii temp;
while (qs.size()!=1){
if (qs.top().second==qt.top().second){
temp=qs.top(),qs.pop();
}
if (qs.top().first>qt.top().second){
return 1;
}
qs.pop(),qt.pop();
if (temp!=ii(-1,-1)){
qs.push(temp);
temp=ii(-1,-1);
}
}
return 0;
}
long long ans=1123456789012345678;
memset(memo,-1,sizeof(memo));
for (int x=0;x<n;x++){
ans=min(ans,tsp(x,((1<<n)-1)^(1<<x) ));
}
/*for (int x=0;x<n;x++){
for (int y=0;y<(1<<n);y++){
printf("%lld ", memo[x][y]);
}
printf("\n");
}*/
return ans;
}
