#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 18;
ll dp[maxn][ 1<< maxn];
int n;
vector<int> s, t;
ll solve(int u, int bit)
{
if(bit + 1 == (1<<n)) return 0;
if(dp[u][bit] != -1) return dp[u][bit];
ll best = 1e18;
for(int v = 0; v< n; v++)
{
if(bit & (1<< v) ) continue;
best = min(best, max(0, t[u]-s[v])+solve(v, bit | (1<<v)));
}
return dp[u][bit] = best;
}
long long plan_roller_coaster(vector<int> _s, vector<int> _t)
{
s = _s, t = _t;
n = (int) s.size();
ll best = 1e18;
memset(dp, -1, sizeof dp);
for(int i = 0; i< n; i++) best = min(best, solve(i, 1<<i));
return best;
}
