#pragma GCC optimize("Ofast")
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
const int MAXN = 5e5+5;
struct node{
int x,lf = -1,rg = -1;
node(){}
};
node T[MAXN*40];
int ccnt = 0;
void pull(int v){
T[v].x = 0;
if(T[v].lf!=-1)T[v].x+=T[T[v].lf].x;
if(T[v].rg!=-1)T[v].x+=T[T[v].rg].x;
}
int copy(int v){
T[++ccnt] = T[v];
return ccnt;
}
int add(int v,int l,int r,int pos,int x){
int me = copy(v);
if(l==r){
T[me].x+=x;
return me;
}
int tm = (l+r)/2;
if(pos<=tm){
if(T[v].lf == -1)T[v].lf = ++ccnt;
T[me].lf = add(T[v].lf,l,tm,pos,x);
}else{
if(T[v].rg == -1)T[v].rg = ++ccnt;
T[me].rg = add(T[v].rg,tm+1,r,pos,x);
}
pull(me);
return me;
}
int query(int v,int l,int r,int tl,int tr){
if(l<=tl && tr<=r)return T[v].x;
int tm = (tl+tr)/2;
if(r<=tm)return T[v].lf == -1?0:query(T[v].lf,l,r,tl,tm);
if(l >tm)return T[v].rg == -1?0:query(T[v].rg,l,r,tm+1,tr);
int res = 0;
res += T[v].lf == -1?0:query(T[v].lf,l,tm,tl,tm);
res += T[v].rg == -1?0:query(T[v].rg,tm+1,r,tm+1,tr);
return res;
}
vector<int>seg;
int n;
void init(int N, int A[], int B[]) {
n = N;
seg.push_back(0);
vector<map<int,int>>cnt(n+1);
for(int i=0;i<n;i++)cnt[A[i]][B[i]]++;
for(int i=1;i<=n;i++){
seg.push_back(copy(seg.back()));
for(auto x:cnt[i]){
//cout<<i<<" "<<x.fi<<" "<<x.se<<'\n';
seg.back() = add(seg.back(),1,n,x.fi,x.se);
}
}
}
int can(int m, int K[]) {
int sum = 0;
map<int,int>cnt;
for(int i=0;i<m;i++){
sum+=K[i];
cnt[K[i]]++;
if(sum>n)return 0;
}
vector<pii>a;
for(auto x:cnt)a.push_back(x);
a.push_back({n+1,0});
int s = a.size();
vector<int>need(s,0);
vector<int>have(s,0);
for(int i=0;i<s;i++)need[i] = a[i].fi * a[i].se;
for(int i=0;i<s;i++){
int l = 0,r = a[i].fi;
if(i)l = a[i-1].fi;
for(int j=i;j+1<s;j++){
int L = a[j].fi;
int R = a[j+1].fi-1;
have[j]+=query(seg[r],L,R,1,n);
have[j]-=query(seg[l],L,R,1,n);
}
for(int j=i;j<s;j++){
if(!need[i])break;
if(have[j]){
int tmp = min(have[j],need[i]);
need[i]-=tmp;
have[j]-=tmp;
}
}
}
for(int x:need){
if(x)return 0;
}
return 1;
}
