#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
#define vec vector
#define int long long
const int MXN = 16;
const int INF = 1e18;
int dist[MXN][MXN];
int dp[MXN][MXN][(1<<MXN) + 1];
long long plan_roller_coaster(std::vector<int32_t> s, std::vector<int32_t> t) {
int n = s.size();
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
if(i==j) continue;
dist[i][j] = max(t[i]-s[i], 0);
}
}
for(int i = 0; i<(1<<n); i++) {
for(int j = 0; j<n; j++) {
for(int k = 0; k<n; k++) {
dp[j][k][i] = INF;
}
}
}
for(int i = 0; i<n; i++) {
dp[i][i][1<<i] = 0;
}
for(int i = 0; i<(1<<n); i++) {
for(int j = 0; j<n; j++) {
//if(j & i != 0) continue;
for(int k = 0; k<n; k++) {
//if(k & i == 0) continue;
for(int l = 0; l<n; l++) {
//if(l & i == 0) continue;
dp[j][k][i | (1<<j)] = min(dp[j][k][i | (1<<j)], dp[l][k][i] + dist[l][j]);
}
}
}
}
int ans = INF;
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
if(i == j) continue;
// cerr << dp[i][j][(1<<n)-1] << ' ';
ans = min(ans, dp[i][j][(1<<n)-1]);
}
}
// cerr << '\n';
// cerr << ans << '\n';
return ans;
}
