#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> s_;
vector<int> t_;
long long mem[17][65537];
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = (int) s.size();
/*if (n<=8){
vector<int> v;
for (int x = 0; x<n; x++){
v.push_back(x);
}
long long ans = 999999999999999;
long long curans = 0;
for (int x = 1; x<n; x++){
curans+=(t[x-1]>s[x])?(t[x-1]-s[x]):0;
}
ans = min(curans,ans);
while (next_permutation(v.begin(),v.end())){
long long curans = 0;
for (int x = 1; x<n; x++){
curans+=(t[v[x-1]]>s[v[x]])?(t[v[x-1]]-s[v[x]]):0;
}
ans = min(curans,ans);
}
return ans;
}
else{*/
memset(mem,-1,sizeof(mem));
for (int x = 0; x<n; x++){
s_.push_back(s[x]);
t_.push_back(t[x]);
}
long long fans = 999999999999999;
for (int bitmask = 0; bitmask<(1<<n); bitmask++){
for (int cur = 0; cur<n; cur++){
if (bitmask==0) {mem[cur][bitmask]=0;continue;}
int cop = bitmask;
long long ans = 999999999999999;
for (int x = 0;cop!=0 ; x++){
if ((cop&(1<<x))!=0){
ans = min(ans,mem[x][bitmask-(1<<x)]+((t_[cur]>s_[x])?(t_[cur]-s_[x]):0));
cop-=(1<<x);
}
//printf("%i\n",x);
}
mem[cur][bitmask] = ans;
}
}
for (int x = 0; x<n; x++){
fans = min(fans,mem[x][(1<<n)-1-(1<<x)]);
}
return fans;
//}
return 0;
}
