#include <bits/stdc++.h>
using namespace std;
struct Node {
int l, r;
int sum;
};
static int N;
static vector<int> roots;
static vector<Node> seg;
static size_t baseSizeAfterInit;
static inline int clone_node(int from) {
seg.push_back(seg[from]);
return (int)seg.size() - 1;
}
static int update_point(int node, int l, int r, int pos) {
int n = clone_node(node);
if (l == r) {
seg[n].sum++;
return n;
}
int mid = (l + r) >> 1;
if (pos <= mid) seg[n].l = update_point(seg[n].l, l, mid, pos);
else seg[n].r = update_point(seg[n].r, mid + 1, r, pos);
seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
return n;
}
static int query_diff(int pref, int used, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return seg[pref].sum - seg[used].sum;
int mid = (l + r) >> 1;
return query_diff(seg[pref].l, seg[used].l, l, mid, ql, qr) +
query_diff(seg[pref].r, seg[used].r, mid + 1, r, ql, qr);
}
static int consume_suffix(int pref, int used, int l, int r, int start, int &need) {
if (need == 0 || r < start) return used;
if (l >= start) {
int avail = seg[pref].sum - seg[used].sum;
if (avail == 0) return used;
if (avail <= need) {
need -= avail;
return pref;
}
if (l == r) {
int n = clone_node(used);
seg[n].sum += need;
need = 0;
return n;
}
}
if (l == r) return used;
int mid = (l + r) >> 1;
int n = clone_node(used);
if (start <= mid)
seg[n].l = consume_suffix(seg[pref].l, seg[used].l, l, mid, start, need);
else
seg[n].l = seg[used].l;
seg[n].r = consume_suffix(seg[pref].r, seg[used].r, mid + 1, r, start, need);
seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
return n;
}
void init(int N_, int A[], int B[]) {
N = N_;
vector<pair<int,int>> students;
students.reserve(N);
for (int i = 0; i < N; i++) students.push_back({A[i], B[i]});
sort(students.begin(), students.end());
size_t reserveNodes = 1ull + 20ull * (size_t)N + 8000000ull;
seg.clear();
seg.reserve(reserveNodes);
seg.push_back({0, 0, 0});
roots.assign(N + 1, 0);
int idx = 0;
for (int s = 1; s <= N; s++) {
int root = roots[s - 1];
while (idx < N && students[idx].first == s) {
root = update_point(root, 1, N, students[idx].second);
idx++;
}
roots[s] = root;
}
baseSizeAfterInit = seg.size();
}
int can(int M, int K[]) {
vector<int> v;
v.reserve(M);
long long total = 0;
for (int i = 0; i < M; i++) {
v.push_back(K[i]);
total += K[i];
if (total > N) return 0;
}
sort(v.begin(), v.end());
int used = 0;
for (int i = 0; i < M; ) {
int s = v[i];
int cnt = 1;
while (i + cnt < M && v[i + cnt] == s) cnt++;
long long need_ll = 1LL * s * cnt;
int need = (int)need_ll;
int pref = roots[s];
int avail = query_diff(pref, used, 1, N, s, N);
if (avail < need) {
seg.resize(baseSizeAfterInit);
return 0;
}
int rem = need;
used = consume_suffix(pref, used, 1, N, s, rem);
i += cnt;
}
seg.resize(baseSizeAfterInit);
return 1;
}
