#include <bits/stdc++.h>
using namespace std ;
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define C continue
typedef long long ll ;
typedef vector < int > vi ;
const ll inf = 1e18 ;
#include "railroad.h"
ll n ;
ll in [17] , out [17] ;
ll dp [(1<<16)+1][17] ;
ll bt ( ll mask , ll last ) {
if ( __builtin_popcount ( mask ) == n ) return 0ll ;
ll &ret = dp [mask][last] ;
if ( ret != -1 ) return ret ;
ret = inf ;
for ( ll nxt = 0 ; nxt < n ; nxt ++ ) {
if ( ( mask & ( 1ll << nxt ) ) ) C ;
ll cost = max ( 0ll , out [last] - in [nxt] ) ;
ret = min ( ret , bt ( mask | ( 1 << nxt ) , nxt ) + cost ) ;
}
return ret ;
}
ll plan_roller_coaster ( vi s , vi t ) {
mem ( dp , - 1 ) ;
n = s.size () ;
for ( int i = 0 ; i < n ; i ++ ) {
in [i] = s [i] ;
out [i] = t [i] ;
}
out [n] = 1ll ;
return bt ( 0 , n ) ;
}
