#include "railroad.h"
#include <iostream>
#include <map>
using namespace std;
typedef vector<int> VI;
typedef long long llong;
const long long INF = 4e18;
int N;
vector<int> S, T;
bool all_visited(const vector<bool>& vis) {
for (int u = 0; u < N; ++u)
if (!vis[u]) return false;
return true;
}
typedef pair< int, vector<bool> > Key;
map<Key, long long> memo;
long long go(int u, const vector<bool>& vis) {
if (all_visited(vis)) {
return 0;
}
if (memo.count( {u, vis} )) {
return memo[ {u, vis} ];
}
long long res = INF;
for (int v = 0; v < N; ++v) {
if (vis[v]) continue;
vector<bool> new_vis = vis;
new_vis[v] = true;
int edge_cost = 0;
if (T[u] > S[v])
edge_cost = T[u] - S[v];
long long cost = go(v, new_vis) + edge_cost;
res = min(res, cost);
}
memo[ {u, vis} ] = res;
return res;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
N = (int) s.size();
if (N > 16) {
return 0;
}
S = s;
T = t;
llong res = INF;
for (int u = 0; u < N; ++u) {
vector<bool> vis(N, false);
vis[u] = true;
long long cur = go(u, vis);
res = min(res, cur);
}
return res;
}
