#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
struct persissegtree{
int vl[1<<24]{},lc[1<<24]{},rc[1<<24]{},CC=0,N_;
void init(int N){
N_=N;
}
int NN(int i){
vl[++CC]=vl[i]+1;
return CC;
}
int NN(int l,int r){
vl[++CC]=vl[l]+vl[r];
lc[CC]=l,rc[CC]=r;
return CC;
}
int updated(int i,int l,int r,int p){
if(l==r)return NN(i);
if(l+r>>1<p)return NN(lc[i],
updated(rc[i],l+r+2>>1,r,p));
return NN(updated(lc[i],l,l+r>>1,p),rc[i]);
}
int qwerwry(int i,int l,int r,int ll,int rr){
if(!i) return 0;
if(l>rr||ll>r) return 0;
if(ll<=l&&r<=rr) return vl[i];
return qwerwry(lc[i],l,l+r>>1,ll,rr)+
qwerwry(rc[i],l+r+2>>1,r,ll,rr);
}
int adto(int node,int ind){
return updated(node,1,N_,ind);
}
int querybef(int node,int ind){
return qwerwry(node,1,N_,1,ind);
}
} APST;
int N_;
vector<pair<int,int>>stuff,stuff2;
vector<int>PWB[500100],lolwhy{0};
void init(int N, int A[], int B[]) {
APST.init(N);
N_=N;
for(int i=0;i<N;i++)
stuff.push_back({A[i],B[i]}),
PWB[N-A[i]+1].push_back(B[i]);
sort(stuff.begin(),stuff.end());
int lstnode=0;
for(int i=1;i<=N;i++){
for(auto y:PWB[i])
lstnode=APST.adto(lstnode,y);
lolwhy.push_back(lstnode);
}
}
int dobig(map<int,int>mp){
int pos=0;
priority_queue<int>pq;
for(auto[i,x]:mp){
while(pos<N_&&stuff[pos].first<=i)
pq.push(-stuff[pos++].second);
while(pq.size()&&-pq.top()<i)
pq.pop();
while(x--){
if(pq.empty())return 0;
pq.pop();
}
}
return 1;
}
int queryallbet(int l,int r){
return APST.querybef(lolwhy[N_-l+1],r-1);
}
int REV[1010];
int dosmall(map<int,int>REQ){
vector<int>pref{0},dp;
int CC=0;
for(auto[x,y]:REQ) REV[++CC]=x,
pref.push_back(pref.back()+y);
pref.push_back(pref.back());
REV[0]=0;
REV[++CC]=N_+1;
dp.resize(pref.size());
int orig=queryallbet(REV[0]+1,REV[CC])-pref.back();
for(int i=1;i<=CC;i++){
dp[i]=dp[i-1];
for(int j=0;j<i;j++){
dp[i]=min(dp[i],dp[j]+pref[i-1]-pref[j]-queryallbet(REV[j]+1,REV[i]));
}
if(-dp[i]>orig)
return 0;
}
return 1;
}
int can(int M, int K[]) {
map<int,int>REQ;
int SM=0;
for(int i=0;i<M;i++) SM+=K[i],
REQ[K[i]]+=K[i],SM=min(N_+1,SM);
if(SM>N_) return 0;
if(M>500) return dobig(REQ);
return dosmall(REQ);
}
