#include "railroad.h"
#include <bits/stdc++.h>
using ll = long long;
struct Track
{
int maxEntrySpeed;
int exitSpeed;
};
int n;
Track tracks[16];
const ll BIG = std::numeric_limits<ll>::max();
ll memo[1 << 16][16];
ll minTrackLen(const uint16_t b, const int l)
{
if (memo[b][l] != 0)
return memo[b][l] - 1;
if (b == (1 << n) - 1)
return 0;
int speed = tracks[l].exitSpeed;
ll m = BIG;
for (int i = 0; i < n; i++)
{
uint16_t mask = 1 << i;
if (b & mask)
continue;
int d = std::max(speed - tracks[i].maxEntrySpeed, 0);
m = std::min(m, minTrackLen(b | mask, i) + d);
}
memo[b][l] = m + 1;
return m;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
if (s.size() > 16)
return 0;
n = s.size();
for (int i = 0; i < n; i++)
{
tracks[i].maxEntrySpeed = s[i];
tracks[i].exitSpeed = t[i];
}
ll m = BIG;
for (int i = 0; i < n; i++)
{
m = std::min(m, minTrackLen(1 << i, i));
}
return m;
}
