#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 17;
long long inf = 1e18 + 10;
int n;
long long dp[(1 << N)][N];
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n = s.size();
if(n >= 17)
return 0;
long long ans = inf;
for(int mask = 1 ; mask < (1 << n) ; mask++) for(int i = 0 ; i < n ; i++)
{
dp[mask][i] = inf;
if(!((mask >> i) & 1))
continue;
if(__builtin_popcount(mask) == 1)
{
dp[mask][i] = 0;
continue;
}
for(int j = 0 ; j < n ; j++) if(j != i && ((mask >> j) & 1))
dp[mask][i] = min(dp[mask][i] , dp[mask - (1 << i)][j] + max(0 , t[j] - s[i]));
}
for(int i = 0 ; i < n ; i++)
ans = min(ans , dp[(1 << n) - 1][i]);
return ans;
}
/*
4
1 7
4 3
5 8
6 6
*/
