#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> s_;
vector<int> t_;
long long mem[17][1000000];
long long recurse(int cur, int bitmask){
if (bitmask==0) return 0;
if (mem[cur][bitmask]!=-1) return mem[cur][bitmask];
int original = bitmask;
long long ans = 999999999999999;
for (int x = 0; ; x++){
if (bitmask==0) break;
if ((bitmask&(1<<x))!=0){
ans = min(ans,recurse(x,original-(1<<x))+((t_[cur]>s_[x])?(t_[cur]-s_[x]):0));
bitmask-=(1<<x);
}
}
return mem[cur][bitmask] = ans;
}
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 ans = 999999999999999;
for (int x = 0; x<n; x++){
ans = min(ans,recurse(x,(1<<n)-1-(1<<x)));
}
return ans;
}
return 0;
}
