#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n;
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);
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
S = s;
T = t;
n = s.size();
multiset<pair<int, int> > aux;
for(int i = 0; i < n; i++){
if(n <= 16) ans = min(ans, getDP(i, (1 << n) - 1));
aux.insert(make_pair(T[i], S[i]));
}
// if(n <= 16) return ans;
int upb = 1e9;
for(int i = 0; i < n; i++){
multiset<pair<int, int> > :: iterator it = aux.upper_bound(make_pair(upb, 1e9));
if(it == aux.begin()) return 1;
it--;
upb = it->second;
aux.erase(it);
}
return 0;
}
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];
}
