#include "railroad.h"
#include <iostream>
using namespace std;
typedef vector<int> VI;
typedef long long llong;
const llong INF = 1e18;
int N;
VI S, T;
bool cached[20][1<<20];
llong memo[20][1<<20];
llong go(int u, int visited_mask) {
if (visited_mask == (1<<N)-1)
return 0;
llong res = memo[u][visited_mask];
if (!cached[u][visited_mask]) {
res = INF;
for (int v = 0; v < N; ++v) {
if (visited_mask & (1<<v)) continue;
llong cost = 0;
if (T[u] > S[v])
cost = T[u] - S[v];
else
cost = 0;
llong t = go(v, visited_mask | (1<<v)) + cost;
res = min(res, t);
}
memo[u][visited_mask] = res;
cached[u][visited_mask] = true;
}
return res;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
N = (int) s.size();
if (N > 20) {
return 0;
}
S = s;
T = t;
llong res = INF;
for (int u = 0; u < N; ++u) {
llong c = go(u, 1<<u);
res = min(res, c);
}
return res;
}
