#include<bits/stdc++.h>
#include "railroad.h"
using namespace std ;
const long long inf = 1e18 ;
const int maxn = 18 ;
long long dp[(1<<maxn)][maxn], n ;
vector<long long> S, T ;
long long solve(int mask, int i){
if(__builtin_popcount(mask) == n+1) return 0 ;
long long &mp = dp[mask][i] ;
if(mp != -1) return mp ;
mp = inf ;
for(int j = 0 ; j <= n ; j++){
if(mask&(1<<j)) continue ;
mp = min(mp, max(0LL, T[i] - S[j]) + solve(mask|(1<<j), j)) ;
}
return mp ;
}
long long plan_roller_coaster(vector<int> s, vector<int> t){
n = (int) s.size() ;
memset(dp, -1, sizeof dp) ;
S.push_back(1), T.push_back(0) ;
for(int i = 0 ; i < n ; i++) S.push_back(s[i]), T.push_back(t[i]) ;
S.push_back(1), T.push_back(0) ;
return solve(1, 0) ;
}
/*
int main(){
cin >> n ;
memset(dp, -1, sizeof dp) ;
S.push_back(1), T.push_back(0) ;
for(int i = 0 ; i < n ; i++){
int a, b ;
cin >> a >> b ;
S.push_back(a), T.push_back(b) ;
}
S.push_back(1), T.push_back(0) ;
cout << solve(1, 0) << "\n" ;
}*/
