#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,cnt[500001],dp[1010],root[500001],st[40000001],le[40000001],ri[40000001],nNode,nRoot,R[500001],pos[500001];
vector <int> v[500001],ve,tmp;
int update(int node, int l, int r, int u, int v){
int mid=(l+r)>>1,cur=++nNode;
st[cur]=st[node];
le[cur]=le[node];
ri[cur]=ri[node];
if (l>=u&&r<=v){
st[cur]++;
return cur;
}
if (u<=mid)
le[cur]=update(le[node],l,mid,u,v);
if (v>mid)
ri[cur]=update(ri[node],mid+1,r,u,v);
return cur;
}
void fakeget(int l=1, int r=n, int u=1, int v=ve.size()-1){
if (u>v||ve[v]<l||ve[u]>r)
return;
if (l==r)
return;
int mid=(l+r)>>1;
pos[mid]=upper_bound(ve.begin(),ve.end(),mid)-ve.begin();
fakeget(l,mid,u,min(v,pos[mid]-1));
fakeget(mid+1,r,max(pos[mid],u),v);
}
int get(int node, int l, int r, int u, int v){
if (u>v||ve[v]<l||ve[u]>r)
return -INF;
if (l==r)
return dp[u]-st[node];
int mid=(l+r)>>1;
return max(get(le[node],l,mid,u,min(v,pos[mid]-1)),get(ri[node],mid+1,r,max(pos[mid],u),v))-st[node];
}
void init(int N, int A[], int B[]){
n=N;
for (int i=0;i<n;i++)
v[A[i]].push_back(B[i]);
for (int i=n;i;i--){
for (int j:v[i]){
nRoot++;
root[nRoot]=update(root[nRoot-1],1,n,i,j);
}
R[i]=root[nRoot];
}
}
int can(int M, int K[]){
int sum=0;
for (int i=0;i<M;i++){
sum+=K[i];
cnt[K[i]]=0;
if (sum>n)
return 0;
}
ve={0};
for (int i=0;i<M;i++){
if (!cnt[K[i]])
ve.push_back(K[i]);
cnt[K[i]]+=K[i];
}
sort(ve.begin(),ve.end());
fakeget();
for (int i=ve.size()-1;i>=0;i--)
dp[i]=max(get(R[ve[i]+1],1,n,i+1,ve.size()-1),0)+cnt[ve[i]];
return (!dp[0]);
}
