#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
int memo[100000][16], vis[100000][16];
int n, inf = 1e18;
vector<signed> s, t;
int dp(int mask, int x){ //taking subset and ending at x
if(vis[mask][x]) return memo[mask][x];
vis[mask][x] = 1;
if(mask == (1<<x)) return memo[mask][x] = 0;
int newmask = mask-(1<<x); //remaining things w/o x
for(int i=0; i<n; i++){
if(i == x) continue;
if(mask&(1<<i)){
int ad = max(t[i] - s[x], 0);
/*if(mask == (1<<n)-1 and x == 2){
dd2(newmask,i)
dd(dp(newmask,i));
dd(ad)
}*/
memo[mask][x] = min(memo[mask][x], dp(newmask,i) + ad);
}
}
return memo[mask][x];
}
long long plan_roller_coaster(vector<signed> S, vector<signed> T) {
s = S, t = T;
n = s.size();
for(int i=0; i<100000; i++) for(int j=0; j<16; j++) memo[i][j] = inf;
int ans = inf, mask = (1<<n)-1;
for(int i=0; i<n; i++){
ans = min(ans, dp(mask,i));
}
return ans;
}
