#include "railroad.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> s, t;
ll dp[1<<19][19];
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
s = sk, t = tk;
n = s.size();
memset(dp, 0x3f3f3f3f, sizeof(dp));
for(int i=0;i<n;i++)dp[0][i] = 0, dp[(1<<i)][i] = 0;
for(int mask = 1; mask < (1<<n); mask++){
for(int en = 0; en < n; en++){
if(!(mask & (1<<en)))continue;
for(int i=0;i<n;i++){
if(!(mask & (1<<i)) || i == en)continue;
dp[mask][en] = min(dp[mask][en], dp[mask^(1<<en)][i] + max(0, t[i] - s[en]));
}
}
}
ll ans = 1e18;
for(int i=0;i<n;i++){
ans = min(ans, dp[(1<<n)-1][i]);
}
return ans;
}
