#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fs first
#define sc second
#define pii pair<int,int>
const int mxn = 5e5+10;
const int BK = 300;
pii arr[mxn];
int N;
int rt[mxn];
struct SEG{
#define mid ((l+r)>>1)
#define ls pl[now]
#define rs pr[now]
const static int LEN = mxn*30;
int pl[LEN],pr[LEN],seg[LEN];
int ptr = 0;
int newnode(int src = 0){
ptr++;
pl[ptr] = pl[src];
pr[ptr] = pr[src];
seg[ptr] = seg[src];
assert(ptr<LEN);
return ptr;
}
int modify(int now,int l,int r,int p){
now = newnode(now);
if(l == r){
seg[now]++;
return now;
}
if(mid>=p)ls = modify(ls,l,mid,p);
else rs = modify(rs,mid+1,r,p);
seg[now] = seg[ls]+seg[rs];
return now;
}
int getval(int tl,int tr,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[tr]-seg[tl];
if(mid>=e)return getval(pl[tl],pl[tr],l,mid,s,e);
else if(mid<s)return getval(pr[tl],pr[tr],mid+1,r,s,e);
else return getval(pl[tl],pl[tr],l,mid,s,e)+getval(pr[tl],pr[tr],mid+1,r,s,e);
}
#undef ls
#undef rs
#undef mid
};
SEG seg;
vector<int> v[mxn];
vector<pii> kids;
void init(int NN, int A[], int B[]) {
N = NN;
for(int i = 0;i<N;i++)v[A[i]].push_back(B[i]);
for(int i = 0;i<N;i++)kids.push_back(pii(A[i],B[i]));
rt[0] = 0;
for(int i = 1;i<=N;i++){
rt[i] = rt[i-1];
for(auto &j:v[i]){
rt[i] = seg.modify(rt[i],1,N,j);
}
}
sort(kids.begin(),kids.end());
return;
}
namespace BRUTE{
int GO(int M,int K[]){
priority_queue<int,vector<int>,greater<int>> pq;
sort(K,K+M);
int ptr = 0;
for(int i = 0;i<M;i++){
while(ptr<kids.size()&&kids[ptr].fs<=K[i]){
pq.push(kids[ptr].sc);
ptr++;
}
while(!pq.empty()&&pq.top()<K[i])pq.pop();
while(K[i]>0&&!pq.empty()){
K[i]--;
pq.pop();
}
if(K[i]>0)return 0;
}
return 1;
}
}
namespace DP{
ll dp[mxn];
int GO(int M,int K[]){
sort(K,K+M);
for(int i = 0;i<M;i++){
dp[i] = seg.getval(rt[0],rt[K[i]],1,N,K[i],N)-K[i];
for(int j = 0;j<i;j++){
ll tval = dp[j]+seg.getval(rt[K[j]],rt[K[i]],1,N,K[i],N)-K[i];
dp[i] = min(dp[i],tval);
if(dp[i]<0)return 0;
}
if(dp[i]<0)return 0;
}
return 1;
}
}
int can(int M, int K[]) {
if(M>=BK)return BRUTE::GO(M,K);
else return DP::GO(M,K);
}
