// ~ Be Name Khoda ~ //
#include "teams.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int lg = 21;
const ll inf = 1e18;
int n;
vector <int> av[maxn5];
namespace seg{
int pt[lg], seg[lg][maxn5], ptl[maxnt], ptr[maxnt];
void build(int l, int r, int v, int h){
if(r - l == 1){
ptl[v] = pt[h];
for(auto u : av[l])
seg[h][pt[h]++] = u;
ptr[v] = pt[h];
sort(seg[h] + ptl[v], seg[h] + ptr[v]);
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2, h + 1);
build(mid, r, v * 2 + 1, h + 1);
ptl[v] = pt[h];
int pt1 = ptl[v * 2], pt2 = ptl[v * 2 + 1];
while(pt1 < ptr[v * 2] || pt2 < ptr[v * 2 + 1]){
if(pt1 < ptr[v * 2] && (pt2 == ptr[v * 2 + 1] || seg[h + 1][pt1] < seg[h + 1][pt2]))
seg[h][pt[h]++] = seg[h + 1][pt1++];
else
seg[h][pt[h]++] = seg[h + 1][pt2++];
}
ptr[v] = pt[h];
}
int get(int l, int r, int lq, int rq, int lq2, int rq2, int v, int h){
if(rq <= l || r <= lq)
return 0;
if(lq <= l && r <= rq){
int x = lower_bound(seg[h] + ptl[v], seg[h] + ptr[v], lq2) - seg[h];
int y = lower_bound(seg[h] + ptl[v], seg[h] + ptr[v], rq2) - seg[h];
return y - x;
}
int mid = (l + r) >> 1;
return get(l, mid, lq, rq, lq2, rq2, v * 2, h + 1) + get(mid, r, lq, rq, lq2, rq2, v * 2 + 1, h + 1);
}
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < n; i++)
av[A[i]].pb(B[i]);
seg::build(0, n + 1, 1, 0);
}
int can(int m, int k[]) {
sort(k, k + m);
int rem = seg::get(0, n + 1, 0, k[0] + 1, k[0], n + 1, 1, 0), used = 0;
for(int i = 0; i < m; i++){
if(rem - used < k[i])
return false;
if(i == m - 1)
return true;
used += k[i];
int er = seg::get(0, n + 1, 0, k[i] + 1, k[i], k[i + 1], 1, 0);
rem -= er;
used = max(0, used - er);
//cout << "hey " << i << ' ' << k[i] << ' ' << rem << ' ' << er << ' ' << used << ' ' << k[i + 1] << endl;
rem += seg::get(0, n + 1, k[i] + 1, k[i + 1] + 1, k[i + 1], n + 1, 1, 0);
//cout << "ok " << rem << endl;
}
return true;
}
