#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#include "railroad.h"
using namespace std;
using namespace __gnu_pbds;
///#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define ff first
#define ss second
#define pb push_back
#define popb pop_back
#define all(x) (x).begin(),(x).end()
const ll INF = 1e18;
const int nax = 16;
int n;
vll s, t;
ll dp[(1 << nax)][nax];
ll f(int mask, int cur)
{
//cout <<mask << ' ' << cur << '\n';
if(mask == (1 << n) - 1)
return dp[mask][cur] = 0ll;
if(dp[mask][cur] != -1)
return dp[mask][cur];
ll ans = INF;
for(int i = 0; i < n; i++)
{
if((1 << i) & mask)
continue;
ans = min(ans, f(mask + (1 << i), i) + max(0ll,s[i] - t[cur]));
}
//cout << cur << ' ' << mask << ' ' << ans << '\n';
return dp[mask][cur] = ans;
}
ll plan_roller_coaster(vi S, vi T)
{
for(auto e: T)
t.pb(e);
for(auto e: S)
s.pb(e);
n = (int) s.size();
ll ans = INF;
memset(dp,-1,sizeof(dp));
for(int i= 0 ; i < n; i++)
{
ans = min(ans, f(( 1<< i), i));
}
return ans;
}
/*
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;
}
*/
