#include "railroad.h"
#define long long long
using namespace std;
const int N = 16;
const long INF = 1LL << 60;
int n, vin[N], vout[N + 1];
long f[N + 1][1 << N];
bool vst[N + 1][1 << N];
void Minimize(long &a, long b) { a = min(a, b); }
long DP(int spd, int mask)
{
if (vst[spd][mask]) return f[spd][mask];
vst[spd][mask] = true;
if (__builtin_popcount(mask) == n) return 0;
f[spd][mask] = INF;
for (int v = 0; v < n; ++v)
if (!((mask >> v) & 1))
Minimize(f[spd][mask], DP(v, mask | (1 << v)) + max(vout[spd] - vin[v], 0));
return f[spd][mask];
}
long plan_roller_coaster(vector<int> s, vector<int> t) {
n = (int) s.size();
for (int i = 0; i < n; ++i)
{
vin[i] = s[i];
vout[i] = t[i];
}
vout[n] = 1;
return DP(n, 0);
}
