#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
int N;
struct Node{
int x, i;
Node* l; Node* r;
Node(){x = i = 0, l = r = nullptr;}
};
Node* root[500500];
int tree[1048577], lazy2[1048577];
bool lazy[1048577];
void build(Node* node, int s, int e){
if (s==e){
node->x = 0; return;
}
int m = (s+e)>>1;
node->l = new Node(); node->r = new Node();
node->l->i = node->i*2, node->r->i = node->i*2+1;
build(node->l, s, m); build(node->r, m+1, e);
node->x = 0;
}
void add(Node* prv, Node* now, int s, int e, int x, int v){
if (s==e){now->x = prv->x+v; return;}
int m = (s+e)>>1;
if (x<=m){
now->l = new Node(); now->l->i = now->i*2;
now->r = prv->r;
add(prv->l, now->l, s, m, x, v);
}
else{
now->l = prv->l;
now->r = new Node(); now->r->i = now->i*2+1;
add(prv->r, now->r, m+1, e, x, v);
}
now->x = now->l->x + now->r->x;
}
int _find(Node* node, int l, int r, int s, int e){
if (r<s || e<l) return 0;
if (s<=l && r<=e) {assert(s==l && r==e); return node->x;}
int m = (l+r)>>1;
return _find(node->l, l, m, s, e) + _find(node->r, m+1, r, s, e);
}
void propagate(int i, int l, int r){
if (!lazy[i]) return;
if (lazy2[i]==-1) tree[i] = 0;
else tree[i] = _find(root[lazy2[i]], 1, N, l, r);
if (l!=r){
lazy[i<<1] = lazy[i], lazy2[i<<1] = lazy2[i];
lazy[i<<1|1] = lazy[i], lazy2[i<<1|1] = lazy2[i];
}
lazy[i] = 0, lazy2[i] = 0;
}
void update(Node* node, int l, int r, int s, int e, int idx){
propagate(node->i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[node->i] = 1;
lazy2[node->i] = idx;
propagate(node->i, l, r);
return;
}
int m = (l+r)>>1;
update(node->l, l, m, s, e, idx); update(node->r, m+1, r, s, e, idx);
tree[node->i] = tree[node->i*2]+tree[node->i*2+1];
}
int XX;
pair<int, int> _lower_bound(Node* node, int l, int r, int e, int k){
propagate(node->i, l, r);
if (e<l) return {-1e9, 0};
if (r<=e && node->x - tree[node->i]<k) return {-1e9, node->x - tree[node->i]};
if (l==r){
XX = k;
return {l, node->x - tree[node->i]};
}
int m = (l+r)>>1;
auto p1 = _lower_bound(node->r, m+1, r, e, k);
if (p1.first!=-1e9) return p1;
k -= p1.second;
auto p2 = _lower_bound(node->l, l, m, e, k);
if (p2.first!=-1e9) return make_pair(p2.first, p2.second+p1.second);
return make_pair(-1e9, p2.second+p1.second);
}
void updatep(int i, int l, int r, int x, int val){
propagate(i, l, r);
if (r<x || x<l) return;
if (l==r) {tree[i] += val; return;}
int m = (l+r)>>1;
updatep(i<<1, l, m, x, val); updatep(i<<1|1, m+1, r, x, val);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
bool cmp(pair<int, int> x1, pair<int, int> x2){
if (x1.second==x2.second) return x1.first<x2.first;
return x1.second>x2.second;
}
vector<pair<int, int>> v;
void init(int n, int A[], int B[]) {
N = n;
root[0] = new Node();
root[0]->i = 1;
build(root[0], 1, n);
v.resize(n);
for (int i=0;i<n;i++) v[i] = {A[i], B[i]};
sort(v.begin(), v.end(), cmp);
for (int i=0;i<n;i++){
root[i+1] = new Node();
root[i+1]->i = 1;
add(root[i], root[i+1], 1, n, v[i].first, 1);
}
}
int can(int M, int K[]) {
//printf("\n");
int s = 0;
for (int i=0;i<M;i++) s += K[i];
if (s>N) return 0;
sort(K, K+M, greater<int>());
update(root[0], 1, N, 1, N, -1);
//printf("%d\n", _find(root[4], 1, N, 2, 2));
for (int i=0;i<M;i++){
int idx = upper_bound(v.begin(), v.end(), make_pair(1e9, K[i]), cmp) - v.begin();
//printf("%d: %d\n", i, idx);
auto p = _lower_bound(root[idx], 1, N, K[i], K[i]);
//printf("%d %d %d\n", p.first, p.second, XX);
if (p.first==-1e9) return 0;
if (p.first+1<=K[i]) update(root[idx], 1, N, p.first+1, K[i], idx);
updatep(1, 1, N, p.first, XX);
}
return 1;
}
