#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int)s.size();
// dp[i][j]: ends at i, visits j
vector<vector<int64_t>> dp(n, vector<int64_t>(1 << n, INT64_MAX));
for (int i = 0; i < n; ++i) dp[i][1 << i] = 0;
for (int visit = 1; visit < (1 << n); ++visit) {
for (int cur = 0; cur < n; ++cur) {
if ((visit & (1 << cur)) == 0) continue;
for (int next = 0; next < n; ++next) {
if (visit & (1 << next)) continue;
// dp[cur][visit] -> dp[next][visit | (1 << next)]
dp[next][visit | (1 << next)] =
min(dp[next][visit | (1 << next)],
dp[cur][visit] + max(t[cur] - s[next], 0));
}
}
}
int64_t minimum = INT64_MAX;
for (int last = 0; last < n; ++last)
minimum = min(minimum, dp[last][(1 << n) - 1]);
return minimum;
}
