#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
long long N;
long long S[1 << 18], T[1 << 18];
long long dp[1 << 16][16];
long long plan_roller_coaster(vector<int> s, vector<int> t) {
N = s.size();
for (int i = 0; i < N; i++) S[i] = s[i];
for (int i = 0; i < N; i++) T[i] = t[i];
// PRCLC
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) dp[i][j] = (1LL << 60);
}
for (int i = 0; i < N; i++) dp[1 << i][i] = 0;
// CALC
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
if (dp[i][j] == (1LL << 60)) continue;
for (int k = 0; k < N; k++) {
if ((i / (1 << k)) % 2 == 1) continue;
long long cost = max(0LL, T[j] - S[k]);
dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + cost);
}
}
}
// FINAL
long long Answer = (1LL << 60);
for (int i = 0; i < N; i++) Answer = min(Answer, dp[(1 << N) - 1][i]);
return Answer;
}
