#include<bits/stdc++.h>
#include "teams.h"
#define ll int
#define F first
#define S second
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair
using namespace :: std;
const ll maxn=5e5+500;
const ll inf=1e9+900;
const ll sq=450;
ll Gn;
ll mna[maxn*4];
ll mxa[maxn*4];
vector<ll> seg[maxn*4];
pii rr[maxn];
void bild(ll l,ll r,ll node){
mna[node]=rr[l].F;
mxa[node]=rr[r-1].F;
for(ll i=l;i<r;i++){
seg[node].pb(rr[i].S);
}
sort(seg[node].begin(),seg[node].end());
if(l+1==r)return;
ll mid=(l+r)/2;
bild(l,mid,2*node);
bild(mid,r,2*node+1);
}
ll findAz(ll l,ll r,ll node=1){
if(l<mna[node])return 0;
if(mxa[node]<=l){
return seg[node].end()-lower_bound(seg[node].begin(),seg[node].end(),r);
}
return findAz(l,r,2*node)+findAz(l,r,2*node+1);
}
void init(int n, int a[], int b[]) {
Gn=n;
for(ll i=0;i<n;i++){
rr[i]=mp(a[i],b[i]);
}
sort(rr,rr+n);
bild(0,n,1);
}
ll ger[sq][sq];
ll tmp[sq];
bool canslow(ll m,ll k[]){
memset(tmp,0,sizeof tmp);
for(ll i=0;i<m;i++){
ll v=k[i];
for(ll j=i;j<m;j++){
tmp[j]+=ger[i][j];
}
for(ll j=i;j<m && v;j++){
if(v<=tmp[j]){
tmp[j]-=v;
v=0;
}else{
v-=tmp[j];
tmp[j]=0;
}
}
if(v)return 0;
}
return 1;
}
void bildGer(ll m,ll k[]){
for(ll t=m;t>=1;t--){
for(ll l=0;l+t-1<m;l++){
ll r=l+t-1;
ger[l][r]=findAz(k[l],k[r]);
if(r+1<m)
ger[l][r]-=ger[l][r+1];
if(l)
ger[l][r]-=ger[l-1][r];
if(l && r+1<m)
ger[l][r]+=ger[l-1][r+1];
}
}
}
ll K[sq];
ll cnt[sq];
int can(int m, int k[]) {
sort(k,k+m);
memset(cnt,0,sizeof cnt);
ll sum=0;
for(ll i=0;i<m;i++){
sum+=k[i];
K[i]=k[i];
}
if(sum>Gn)return 0;
ll sz=unique(K,K+m)-K;
for(ll i=0;i<m;i++){
ll t=(lower_bound(K,K+sz,k[i])-K);
cnt[t]++;
}
bildGer(sz,K);
for(ll i=0;i<sz;i++){
K[i]*=cnt[i];
}
return canslow(sz,K);
}
