#include <bits/stdc++.h>
#include "railroad.h"
template <class T>
using Vec = std::vector<T>;
constexpr long long INF = std::numeric_limits<long long>::max() / 2;
long long plan_roller_coaster(Vec<int> s, Vec<int> t) {
const int n = (int) s.size();
if (n <= 16) {
Vec<Vec<long long>> dp(1 << n, Vec<long long>(n, INF));
for (int i = 0; i < n; ++i) {
dp[1 << i][i] = 0;
}
for (int set = 0; set < (1 << n); ++set) {
for (int last = 0; last < n; ++last) {
if (!(set >> last & 1)) {
continue;
}
for (int next = 0; next < n; ++next) {
if (set >> next & 1) {
continue;
}
auto &val = dp[set | (1 << next)][next];
val = std::min(val, dp[set][last] + std::max(t[last] - s[next], 0));
}
}
}
long long ret = INF;
for (int i = 0; i < n; ++i) {
ret = std::min(ret, dp[(1 << n) - 1][i]);
}
return ret;
}
std::priority_queue<std::pair<int, int>> que;
for (int i = 0; i < n; ++i) {
que.emplace(s[i], i);
}
Vec<int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
return t[i] > t[j];
});
int match = 0;
for (const auto i: ord) {
bool re_insert = false;
while (t[i] <= que.top().first) {
const auto j = que.top().second;
que.pop();
if (i == j) {
re_insert = true;
}
else {
match += 1;
}
}
match -= 1;
if (match < 0) {
return 1;
}
if (re_insert) {
que.emplace(s[i], i);
}
}
return 0;
}
