#pragma once
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
const int len = 2e7 + 5;
int sum[len], ls[len], rs[len], l[len], r[len], cnt = 0;
int build(int li, int ri)
{
int vr = cnt++;
l[vr] = li, r[vr] = ri, sum[vr] = 0;
if (li != ri) ls[vr] = build(li, (li + ri) / 2), rs[vr] = build((li + ri) / 2 + 1, ri);
return vr;
}
int upd(int i, int vr) // vrati novy koren
{
if (i < l[vr] || i > r[vr]) return vr;
int v2 = cnt++;
sum[v2] = sum[vr] + 1;
l[v2] = l[vr], r[v2] = r[vr];
if (l[vr] != r[vr]) ls[v2] = upd(i, ls[vr]), rs[v2] = upd(i, rs[vr]);
return v2;
}
int query(int li, int ri, int vr)
{
if (ri < l[vr] || li > r[vr]) return 0;
if (li <= l[vr] && r[vr] <= ri) return sum[vr];
return query(li, ri, ls[vr]) + query(li, ri, rs[vr]);
}
vector<int> ro;
int n;
void init(int N, int A[], int B[])
//void init(int N, vector<int> A, vector<int> B)
{
n = N, cnt = 0;
ro.resize(N + 1);
vector<vector<int> > e(N + 1);
for (int i = 0; i < N; i++) e[A[i]].push_back(B[i]);
ro[0] = build(0, N);
for (int i = 0; i <= N; i++)
{
if (i) ro[i] = ro[i - 1];
for (int x : e[i]) ro[i] = upd(x, ro[i]);
}
}
int can(int M, int K[])
//int can(int M, vector<int> K)
{
int s = 0;
for (int i = 0; i < M; i++) s += K[i];
if (s > n) return 0;
sort(K, K + M);
//sort(K.begin(), K.end());
vector<pair<int, int> > v;
for (int i = 0; i < M; i++)
{
if (!i || v.back().first != K[i]) v.push_back({ K[i], 0 });
v.back().second += K[i];
}
vector<int> dp(v.size(), 0); // najvacsie mozne places - kids
for (int ri = v.size() - 1; ri >= 0; ri--)
{
dp[ri] = v[ri].second - (query(v[ri].first, n, ro[v[ri].first]));
if (dp[ri] > 0) return 0;
int mx = -1e9;
for (int li = ri + 1; li < v.size(); li++) if (dp[li] > mx)
{
mx = dp[li];
dp[ri] = max(dp[ri], dp[li] + v[ri].second - query(v[ri].first, v[li].first - 1, ro[v[ri].first]));
if (dp[ri] > 0) return 0;
}
}
return 1;
}
