#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>
const ll inf = 1e18;
const int mxn = 18;
ll paths[mxn][mxn];
ll dp[mxn][1<<mxn];
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int N = (int)s.size();
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
paths[i][j] = max(0,t[i]-s[j]);
}
}
for(auto &i:dp)for(auto &j:i)j = inf;
for(int i = 0;i<N;i++){
dp[i][1<<i] = 0;
}
for(int i = 0;i<(1<<N);i++){
for(int j = 0;j<N;j++){
if(!(i&(1<<j)))continue;
for(int k = 0;k<N;k++){
if(i&(1<<k))continue;
dp[k][i^(1<<k)] = min(dp[k][i^(1<<k)],dp[j][i]+paths[j][k]);
}
}
}
ll ans = inf;
for(int i = 0;i<N;i++)ans = min(ans,dp[i][(1<<N)-1]);
return ans;
}
