#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n;
vector<int> ord;
vector<int> S, T;
long long ans = 1e18;
long long dp[20][1<<18];
bool marc[20][1<<18];
long long getDP(int cur, int mask);
void bt(int i, long long sum);
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
S = s;
T = t;
n = s.size();
ord = vector<int> (n);
for(int i = 0; i < n; i++){
ans = min(ans, getDP(i, (1 << n) - 1));
ord[i] = i;
}
// bt(0, 0);
return ans;
}
long long getDP(int cur, int mask){
if(marc[cur][mask]) return dp[cur][mask];
marc[cur][mask] = 1;
dp[cur][mask] = INF;
if(!((1 << cur) & mask)) return dp[cur][mask] = INF;
if(!((1 << cur) ^ mask)) return dp[cur][mask] = 0;
for(int i = 0; i < n; i++)
dp[cur][mask] = min(dp[cur][mask], getDP(i, mask ^ (1 << cur)) + max(0, T[i] - S[cur]));
return dp[cur][mask];
}
void bt(int i, long long sum){
if(sum > ans) return;
if(i == n){
ans = sum;
return;
}
for(int j = i; j < n; j++){
swap(ord[i], ord[j]);
if(i != 0) sum += max(T[ord[i - 1]] - S[ord[i]], 0);
bt(i + 1, sum);
if(i != 0) sum -= max(T[ord[i - 1]] - S[ord[i]], 0);
swap(ord[i], ord[j]);
}
}
