#include <bits/stdc++.h>
#include "railroad.h"
template <class T>
using Vec = std::vector<T>;
constexpr long long INF = std::numeric_limits<long long>::max() / 2;
long long plan_roller_coaster(Vec<int> s, Vec<int> t) {
const int n = (int) s.size();
assert(n <= 16);
Vec<Vec<long long>> dp(1 << n, Vec<long long>(n, INF));
for (int i = 0; i < n; ++i) {
dp[1 << i][i] = 0;
}
for (int set = 0; set < (1 << n); ++set) {
for (int last = 0; last < n; ++last) {
if (!(set >> last & 1)) {
continue;
}
for (int next = 0; next < n; ++next) {
if (set >> next & 1) {
continue;
}
auto &val = dp[set | (1 << next)][next];
val = std::min(val, dp[set][last] + std::max(t[last] - s[next], 0));
}
}
}
long long ret = INF;
for (int i = 0; i < n; ++i) {
ret = std::min(ret, dp[(1 << n) - 1][i]);
}
return ret;
}
