#include "teams.h"
#include "bits/stdc++.h"
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#define pb push_back
#define all(v) v.begin(),v.end()
#define ub upper_bound
#define lb lower_bound
#define sz(s) (int)s.size()
const int MAX=5e5+10;
int n;
vector<int> b[MAX];
struct segtree1{
int t[40*MAX];
int l[40*MAX],r[40*MAX];
int cnt;
segtree1(){
cnt=0;
memset(t,0,sizeof(t));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
}
void build(int v,int tl,int tr){
if(tl==tr)return;
int tm=(tl+tr)/2;
l[v]=++cnt,r[v]=++cnt;
build(l[v],tl,tm);
build(r[v],tm+1,tr);
}
int update(int v,int tl,int tr,int pos){
if(tl==tr){
int cur=++cnt;
t[cur]=t[v]+1;
return cur;
}
int tm=(tl+tr)/2;
int cur=++cnt;
if(pos<=tm){
l[cur]=update(l[v],tl,tm,pos);
r[cur]=r[v];
}
else{
r[cur]=update(r[v],tm+1,tr,pos);
l[cur]=l[v];
}
t[cur]=t[l[cur]]+t[r[cur]];
return cur;
}
int get(int v,int tl,int tr,int L,int R){
if(L>R||L>tr||tl>R)return 0;
if(L<=tl&&tr<=R)return t[v];
int tm=(tl+tr)/2;
return get(l[v],tl,tm,L,R)+get(r[v],tm+1,tr,L,R);
}
}z;
vector<int> roots;
void init(int N, int A[], int B[]){
n=N;
for(int i=0;i<N;i++){
b[A[i]].pb(B[i]);
}
z.build(0,1,n);
roots.pb(0);
for(int i=1;i<=n;i++){
for(int pos:b[i]){
if(sz(roots)==i){
roots.pb(z.update(roots.back(),1,n,pos));
}
else{
int v=roots.back();
roots.pop_back();
roots.pb(z.update(v,1,n,pos));
}
}
if(b[i].empty()){
roots.pb(roots.back());
}
}
// cout<<sz(roots)<<"\n";
}
int cnt[MAX],dp[MAX];
int can(int M, int K[]){
sort(K,K+M);
int sum=0;
vector<int> a;
for(int i=0;i<M;i++){
sum+=K[i];
cnt[K[i]]++;
a.pb(K[i]);
}
if(sum>n)return 0;
sort(all(a));
a.erase(unique(all(a)),a.end());
// cout<<z.get(roots[3],1,n,3,n)<<"\n";
for(int x:a){
dp[x]=z.get(roots[x],1,n,x,n)-cnt[x]*x;
for(int y:a){
if(y>=x)break;
dp[x]=min(dp[x],dp[y]+z.get(roots[x],1,n,x,n)-z.get(roots[y],1,n,x,n)-cnt[x]*x);
}
// cerr<<x<<" "<<dp[x]<<"\n";
if(dp[x]<0){
for(int y:a)cnt[y]=0;
return 0;
}
}
for(int y:a)cnt[y]=0;
return 1;
}
