#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define all(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define bk back()
const int MOD = 1000000007;
const int mx = 500005;
int N;
int A[mx];
int B[mx];
vpi students;
int pref[mx];
int suf[mx];
void init(int _N, int _A[], int _B[]) {
N = _N;
for(int i = 0; i < N; i++){
A[i] = _A[i]; B[i] = _B[i];
}
for(int i = 0; i < N; i++){
students.pb(mp(A[i], B[i]));
}
sort(all(students));
for(int i = 0; i < N; i++){
pref[students[i].s]++;
suf[students[i].f]++;
}
for(int i = N; i >= 1; i--){
suf[i]+=suf[i+1];
}
for(int i = 1; i <= N; i++){
pref[i]+=pref[i-1];
}
}
int can(int M, int _K[]) {
vi K;
int Ksum = 0;
for(int i = 0; i < M; i++){
K.pb(_K[i]);
Ksum+=K[i];
if(Ksum > N) return 0;
}
sort(all(K));
vpi pv; // position, value --> csum
for(int i = 0; i < M; i++){
pv.pb(mp(K[i], 0));
for(int j = i; j < M; j++){
if(K[j] == K[i]){
pv.bk.s+=K[j];
i = j;
}
else{
break;
}
}
}
for(int i = 1; i < sz(pv); i++){
pv[i].s+=pv[i-1].s;
}
vi num1, num2;
num1.pb(pref[pv[0].f-1]);
for(int i = 1; i < sz(pv); i++){
num1.pb(pref[pv[i].f-1]-pv[i-1].s);
}
for(int i = 0; i < sz(pv); i++){
num2.pb(suf[pv[i].f+1]+pv[i].s);
}
int curmax = -MOD;
int maxval = -MOD;
for(int i = 0; i < sz(pv); i++){
curmax = max(curmax, num1[i]);
maxval = max(maxval, curmax+num2[i]);
}
if(maxval > N) return 0;
return 1;
}
