#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct Segtree {
vector<array<ll,2>> seg;int n;
Segtree(int sz) {
n = sz;
seg.assign(2*n, {0, 0});
}
array<ll, 2> combine(array<ll, 2> a, array<ll, 2> b) {
if (a[0] < b[0]) return a;
return b;
}
void st(int i, int v) {
i+=n;
seg[i] = {v, i-n};
for (;i>1;i>>=1) {
seg[i>>1] = min(seg[i], seg[i^1]);
}
}
array<ll,2> get(int l, int r) {
array<ll,2> res = {(int)1e18, 0};
for (l += n, r+=n; l<r;l>>=1,r>>=1) {
if ((l & 1)) res = combine(res, seg[l++]);
if ((r&1)) res = combine(res, seg[--r]);
}
return res;
}
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = (int) s.size();
if (n <= 16) {
vector<vector<ll>> dp((1<<n), vector<ll>(n, 1e18));
for (int i=1;i<(1<<n);i++) {
if (__builtin_popcount(i) == 1) {
for (int j=0;j<n;j++) dp[i][j]=0;
continue;
}
for (int j=0;j<n;j++) {
if ((i & (1<<j)) == 0) continue;
for (int k=0;k<n;k++) {
if (k == j || (i & (1<<k)) == 0) continue;
ll val = dp[i ^ (1<<j)][k] + max(0, t[k]-s[j]);
dp[i][j] = min(dp[i][j], val);
}
}
}
ll mn = 1e18;
for (int i=0;i<n;i++) {
mn = min(mn, dp.back()[i]);
}
return mn;
}
// check if the answer can be zero
vector<array<int,2>> v(n);
for (int i=0;i<n;i++) {
v[i]={s[i], t[i]};
}
sort(v.begin(), v.end());
for (int i=0;i<n;i++) {
s[i]=v[i][0];
t[i]=v[i][1];
}
Segtree sg(n);
for (int i=0;i<n;i++) {
sg.st(i, t[i]);
}
int velo = 1;
for (int i=0;i<n;i++) {
auto it = lower_bound(s.begin(), s.end(), velo);
if (it == s.end()) return 1;
int idx = distance(s.begin(), it);
auto res = sg.get(idx, n);
if (res[0] == (int)1e18) return 1;
velo = res[0];
sg.st(res[1], (int)1e18);
}
return 0;
}
