// clang-format off
#include <bits/stdc++.h>
int N;
std::vector<int> A, B;
void init(int n, int a[], int b[]) {
N = n;
A.resize(N);
B.resize(N);
for (int i = 0; i < N; ++i) {
A[i] = a[i];
B[i] = b[i];
}
}
int internal_can(const int M, std::vector<int> K) {
int sum = 0;
// overflow
for (int i = 0; i < M; ++i) {
sum += K[i];
if (sum > N) return 0;
}
std::sort(K.begin(), K.end());
std::vector<std::pair<int, int>> teams;
{
for (int i = 0; i < M; ++i) {
if (i == 0 or K[i] != K[i - 1]) {
teams.push_back({K[i], 1});
} else {
++teams.back().second;
}
}
}
std::vector<int> values;
values.reserve(teams.size() + 1);
for (const auto &[a, b] : teams) values.push_back(a);
values.push_back(N + 1);
const int L = (int)values.size();
// L : sqrt(N) ?
std::vector<std::vector<int>> people(L + 1, std::vector<int>(L + 1));
// naive
std::vector<int> prd(N + 2);
for (int i = 0; i < L; ++i) {
int l = i == 0 ? 1 : (values[i - 1] + 1);
for (int j = l; j <= values[i]; ++j) prd[j] = i;
}
for (int i = 0; i < N; ++i) ++people[prd[A[i]]][prd[B[i] + 1]];
std::vector<int> data(L + 1);
for (int i = 0; i < L; ++i) {
for (int j = 0; j <= L; ++j) data[j] += people[i][j];
while (teams[i].second--) {
int c = teams[i].first;
for (int j = i + 1; j <= L; ++j) {
if (c > data[j]) {
c -= data[j];
data[j] = 0;
} else {
data[j] -= c;
c = 0;
break;
}
}
if (c != 0) return 0;
}
}
return 1;
}
int can(int M, int K[]) {
std::vector<int> k(M);
for (int i = 0; i < M; ++i) k[i] = K[i];
return internal_can(M, k);
}
