#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
long long memo[18][65541];
int N;
int S[200008];
int T[200008];
long long dp(int cur, int state){
if(state == 0){
return 0;
}else if(memo[cur][state] != -1){
return memo[cur][state];
}else if(cur == 17){
long long ans = 1LL << 62;
for(int i = 0; i < N; i ++){
ans = min(ans, dp(i, state^(1<<i)));
}
return ans;
}else{
long long ans = 1LL << 62;
for(int i = 0; i < N; i ++){
if(state&(1<<i)){
ans = min(ans, max(T[cur]-S[i], 0) + dp(i, state^(1<<i)));
}
}
return memo[cur][state] = ans;
}
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
N = (int) s.size();
for(int i = 0; i < N; i ++){
S[i] = s[i];
T[i] = t[i];
//printf("x: %d %d\n", S[i], T[i]);
}
memset(memo, -1, sizeof(memo));
return dp(17, (1<<N)-1);
}
/*
#include <cstdio>
#include <cassert>
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> s(n), t(n);
for (int i = 0; i < n; ++i)
assert(2 == scanf("%d%d", &s[i], &t[i]));
long long ans = plan_roller_coaster(s, t);
printf("%lld\n", ans);
return 0;
}
*/
