// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "railroad.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll dp[1<<16][16];
void minim(ll &a, ll b){
a = min(a, b);
}
ll plan_roller_coaster(vector<int> a, vector<int> b){
int n = sz(a);
for(int msk = 0; msk < (1<<n); msk++){
for(int i = 0; i < n; i++){
dp[msk][i] = inf;
if(bit(msk, i) && __builtin_popcount(msk) == 1)
dp[msk][i] = 0;
}
}
for(int msk = 1; msk < (1<<n); msk++){
for(int i = 0; i < n; i++){
if(bit(msk, i) == 0)
continue;
for(int j = 0; j < n; j++){
if(i == j || bit(msk, j))
continue;
minim(dp[msk | (1<<j)][j], dp[msk][i] + max(int(0), b[i] - a[j]));
}
}
}
ll ans = inf;
for(int i = 0; i < n; i++){
ans = min(ans, dp[(1<<n)-1][i]);
}
return ans;
}
