#include <bits/stdc++.h>
#include "railroad.h"
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define inf 1000000000000000000ll
#define infmale 2000000000ll
using namespace std;
typedef long long ll;
struct przedzialowiec{
int n;
vector<vector<ll>> liscie;
vector<ll> mini;
przedzialowiec(int nn){
for(n = 1; n < nn;) n <<= 1;
liscie.resize(n<<1);
mini.resize(n<<1, inf);
}
void wrzuc(int poz, ll wart){
liscie[poz+n-1].emplace_back(wart);
}
void zbuduj(){
FOR(i, n, n+n-1){
sort(liscie[i].begin(), liscie[i].end(), greater<ll>());
if(liscie[i].size()) mini[i] = liscie[i].back();
}
for(int i = n; --i;) mini[i] = min(mini[i<<1], mini[i<<1|1]);
}
ll mini_prz(int p, int k, int tp, int tk, int w){
if(p <= tp && tk <= k) return mini[w];
int sr = (tp+tk)>>1;
ll ret = inf;
if(p <= sr) ret = min(ret, mini_prz(p, k, tp, sr, w<<1));
if(sr < k) ret = min(ret, mini_prz(p, k, sr+1, tk, w<<1|1));
return ret;
}
ll mini_prz(int p, int k){
return mini_prz(p, k, 1, n, 1);
}
void usun(int poz){
poz += n-1;
liscie[poz].pop_back();
mini[poz] = liscie[poz].size() ? liscie[poz].back() : inf;
while(poz >>= 1) mini[poz] = min(mini[poz<<1], mini[poz<<1|1]);
}
};
ll plan_roller_coaster(vector<int> s, vector<int> t) {
int n = s.size();
if(n <= 16){
vector<vector<ll>> dp(1<<n, vector<ll>(n, inf));
FOR(maska, 1, (1<<n)-1) REP(ost, n) if(maska>>ost&1){
if(__builtin_popcount(maska) == 1) dp[maska][ost] = 0ll;
REP(i, n) if(!(maska>>i&1)) dp[maska+(1<<i)][i] = min(dp[maska+(1<<i)][i], dp[maska][ost] + max(0, t[ost]-s[i]));
}
ll wyn = inf;
REP(i, n) wyn = min(wyn, dp[(1<<n)-1][i]);
return wyn;
}
set<int> secik;
for(int x : s) secik.emplace(x);
for(int x : t) secik.emplace(x);
unordered_map<int, int> mapa;
int it = 0;
for(int x : secik) mapa[x] = ++it;
for(int &x : s) x = mapa[x];
for(int &x : t) x = mapa[x];
int ost = 1;
przedzialowiec prz(it);
REP(i, n) prz.wrzuc(s[i], t[i]*infmale+s[i]);
prz.zbuduj();
REP(xd, n){
ll mini = prz.mini_prz(ost, it);
if(mini == inf) return 1ll;
ost = mini/infmale;
prz.usun(mini%infmale);
// i = gosc o minimalnym t[i] sposrod gosci o s[i]>=ost
// nie istnieje? return 1ll;
// ost = t[i]
// wywal goscia i
}
return 0ll;
}
