#ifdef LOCAL
#include "grader.cpp"
#endif
#include "railroad.h"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
int n;
LL dp[16][1<<16], edge[16][16];
struct A{
LL w;
int u, b;
bool operator <(const A& o) const{
return w>o.w;
}
};
priority_queue<A> dijk;
LL plan_roller_coaster(vector<int> s, vector<int> t) {
n = SZ(s);
int i,j;
for(i=0;i<n;i++){
for(j=0;j<(1<<n);j++) dp[i][j] = 1e18;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i==j) edge[i][j] = 0;
else edge[i][j] = max(0, t[i]-s[j]);
}
}
for(i=0;i<n;i++){
dp[i][1<<i] = 0;
dijk.push({0, i, 1<<i});
}
while(!dijk.empty()){
int u = dijk.top().u;
LL w = dijk.top().w;
int b = dijk.top().b;
dijk.pop();
for(i=0;i<n;i++){
if(i==u || (b&(1<<i))) continue;
if(dp[i][b|(1<<i)] > w + edge[u][i]){
dp[i][b|(1<<i)] = w + edge[u][i];
dijk.push({dp[i][b|(1<<i)], i, b|(1<<i)});
}
}
}
LL ans = 1e18;
for(i=0;i<n;i++) ans = min(ans, dp[i][(1<<n)-1]);
return ans;
}
