#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
int n,cnt[500001],dp[1010],root[500001],st[40000001],le[40000001],ri[40000001],nNode,nRoot,R[500001];
vector <int> v[500001];
int update(int node, int l, int r, int u, int v){
if (l>=u&&r<=v){
nNode++;
st[nNode]=st[node]+1;
le[nNode]=le[node];
ri[nNode]=ri[node];
return nNode;
}
int mid=(l+r)>>1,cur=++nNode;
st[cur]=st[node];
le[cur]=le[node];
ri[cur]=ri[node];
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;
}
int get(int node, int l, int r, int x){
if (l>x||r<x||!node)
return 0;
if (l==r)
return st[node];
int mid=(l+r)>>1;
return get(le[node],l,mid,x)+get(ri[node],mid+1,r,x)+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];
if (sum>n)
return 0;
}
vector <int> ve;
for (int i=0;i<M;i++){
cnt[K[i]]++;
if (cnt[K[i]]==1)
ve.push_back(K[i]);
}
ve.push_back(0);
sort(ve.begin(),ve.end());
for (int i=ve.size()-1;i>=0;i--){
dp[i]=0;
for (int j=i+1;j<ve.size();j++)
dp[i]=max(dp[i],dp[j]+ve[j]*cnt[ve[j]]-get(R[ve[i]+1],1,n,ve[j]));
}
for (int i=0;i<M;i++)
cnt[K[i]]=0;
return (!dp[0]);
}
