#include <bits/stdc++.h>
#include "railroad.h"
#define MAX 20
#define EXP 1024*64 + 10
#define INF 1000000000000000000LL
using namespace std;
typedef long long int lli;
int N;
int S[MAX];
int T[MAX];
lli dp[MAX][EXP];
bool isActive(int i, int mask) { return mask & (1 << i); }
lli cost(int i, int j)//estou no i e vou entrar no j
{
if(S[j] >= T[i]) return 0;
return T[i] - S[j];
}
lli DP(int i, int mask)
{
//printf("i = %d ask = %d\n",i,mask);
if(dp[i][mask] != -1) return dp[i][mask];
if(mask == (1 << i)) return dp[i][mask] = 0;
dp[i][mask] = INF;
for(int g = 0 ; g < N ; g++)
{
if(!isActive(g , mask) || g == i) continue;
dp[i][mask] = min(dp[i][mask] , DP(g , mask - (1 << i)) + cost(g , i));
}
//printf("dp(%d,%d) = %lld\n",i,mask,dp[i][mask]);
return dp[i][mask];
}
long long int plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
N = s.size();
memset(dp , -1 , sizeof(dp));
for(int g = 0 ; g < N ; g++)
{
S[g] = s[g];
T[g] = t[g];
}
lli ans = INF;
for(int g = 0 ; g < N ; g++)
ans = min(ans , DP(g , (1 << N) - 1));
return ans;
}
/*int main()
{
scanf("%d",&N);
vector<int> ss(N), tt(N);
for(int g = 0 ; g < N ; g++)
scanf("%d",&ss[g]);
for(int g = 0 ; g < N ; g++)
scanf("%d",&tt[g]);
printf("%lld\n",plan_roller_coaster(ss , tt));
}*/
