#include <bits/stdc++.h>
#include "teams.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
vector<ll> seg[2000009];
void add(ll v, ll tl, ll tr, ll idx, ll val){
seg[v].pb(val);
if(tl == tr) return;
if(idx <= (tl+tr)/2)
add(2*v, tl, (tl+tr)/2, idx, val);
else
add(2*v+1, (tl+tr)/2+1, tr, idx, val);
}
int get(ll v, ll tl, ll tr, ll l, ll r, ll val){
if(tr < l || r < tl)
return 0;
else if(l <= tl && tr <= r){
return seg[v].end()-lower_bound(all(seg[v]), val);
}
else{
return get(2*v, tl, (tl+tr)/2, l, r, val) + get(2*v+1, (tl+tr)/2+1, tr, l, r, val);
}
}
ll n;
void init(int N, int A[], int B[]){
n = N;
for(ll i = 0; i < N; ++i){
add(1, 1, N, A[i], B[i]);
}
for(ll i = 1; i <= 4*n+5; ++i)
sort(all(seg[i]));
}
int can(int M, int K[]){
sort(K, K+M);
vector<ll> dp(M);
vector<ll> use;
for(ll i = 0; i < M; ++i){
dp[i] = get(1, 1, n, 1, K[i], K[i])-K[i];
while(use.size() >= 2){
ll v1 = dp[use[use.size()-2]] + get(1, 1, n, K[use[use.size()-2]]+1, K[i], K[i]);
ll v2 = dp[use[use.size()-1]] + get(1, 1, n, K[use[use.size()-1]]+1, K[i], K[i]);
if(v1 <= v2)
use.pop_back();
else
break;
}
if(use.size())
dp[i] = min(dp[i], dp[use.back()] + get(1, 1, n, K[use.back()]+1, K[i], K[i])-K[i]);
use.pb(i);
if(dp[i] < 0){
return 0;
}
}
return 1;
}
