#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 16;
const long long INF = 1e18;
int st[nax], en[nax];
int n;
long long dp[1<<nax][nax];
long long solve(int mask, int prev = 0) {
if(mask==(1<<n)-1) return 0LL;
long long &ret = dp[mask][prev];
if(ret!=-1) return ret;
ret = INF;
for(int i=0; i<n; ++i) if(~mask>>i&1) {
int last_speed = en[prev];
if(mask==0) last_speed = 1;
long long track = max(0, last_speed - st[i]);
ret = min(ret, track + solve((mask|(1<<i)), i));
}
return ret;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
n = (int) s.size();
for(int i=0; i<n; ++i) {
st[i] = s[i], en[i] = t[i];
}
memset(dp, -1, sizeof dp);
return solve(0);
}
