#include "railroad.h"
#include <bits/stdc++.h>
using namespace std ;
const int N = 16 ;
const long long oo = 1e15 ;
long long dp [(1<<N)][N+1] ;
int mk = 0 ;
int n = 0 ;
int S[N+2], T[N+2] ;
long long go ( int mask, int lst ) {
if ( mk == mask ) return 0 ;
auto &rf = dp[mask][lst] ;
if ( rf!=-1 ) return rf;
rf = oo ;
for ( int j = 0 ; j < n ; ++j ) {
if ( mask & (1<<j) ) continue ;
int v = 0 ;
if ( mask ) v = max ( 0, T[lst] - S[j]) ;
rf = min ( rf, go (mask | (1<<j), j) + v ) ;
}
return rf ;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n = (int) s.size();
mk = (1<<n)-1 ;
for ( int i = 0 ; i < n ; ++i ) S[i] = s[i], T[i] = t[i] ;
memset ( dp, -1, sizeof dp ) ;
return go ( 0, 0 );
}
