#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "teams.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
const int MAXN = (int)5e5 + 7;
typedef long long ll;
using namespace std;
int N;
vector < pair <int, int > > a;
int sz;
int root[MAXN];
vector <int> q[MAXN];
ll dp[MAXN];
struct tree {
int t[MAXN * 30], ls[MAXN * 30], rs[MAXN * 30];
inline void upd(int p, int &v, int lv, int tl = 1, int tr = MAXN) {
v = ++sz;
if (tl == tr) {
t[v] = t[lv] + 1;
return;
}
int tm = tl + tr >> 1;
if (p <= tm) rs[v] = rs[lv], upd(p, ls[v], ls[lv], tl, tm);
else ls[v] = ls[lv], upd(p, rs[v], rs[lv], tm + 1, tr);
t[v] = t[ls[v]] + t[rs[v]];
}
inline int get(int l, int r, int v, int tl = 1, int tr = MAXN) {
//cerr << tl << ' ' << tr << ' ' << v << endl;
if (tl > r || tr < l || !v) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = tl + tr >> 1;
return get(l, r, ls[v], tl, tm) + get(l, r, rs[v], tm + 1, tr);
}
} t;
void init(int _N, int A[], int B[]) {
N = _N;
for (int i = 0; i < N; i++) {
a.pb({A[i], B[i]});
q[A[i]].pb(B[i]);
}
root[0] = ++sz;
for (int i = 1; i < MAXN; i++) {
root[i] = root[i - 1];
for (auto it : q[i]) {
t.upd(it, root[i], root[i]);
}
}
}
int can(int M, int K[]) {
sort (K, K + M);
ll sum = 0;
vector < pair <int, int> > k;
for (int i = 0; i < M; i++) {
if (!sz(k) || k.back().f != K[i]) k.pb({K[i], 1});
else k.back().s++;
sum += K[i];
}
if (sum > sz(a)) return 0;
for (int i = 0; i < sz(k); i++) {
int cnt = t.get(k[i].f, MAXN, root[k[i].f]);
ll cur = (ll)k[i].f * k[i].s;
if (cnt < cur) return 0;
dp[i] = 0;
for (int j = i - 1; j >= 0; j--) {
int com = t.get(k[i].f, MAXN, root[k[j].f]);
dp[i] = max(dp[i], dp[j] + com);
}
dp[i] += cur - cnt;
if (dp[i] > 0) return 0;
}
return 1;
}
