#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// --- Persistent Segment Tree ---
// Allows querying: count students with B >= Y within a range of A values.
const int MAXN = 500005;
const int MAX_NODES = MAXN * 25;
struct Node {
int l, r;
int sum;
} tree[MAX_NODES];
int roots[MAXN]; // roots[i] stores the segment tree for students with A <= i
int node_cnt = 0;
int N_global;
// Build an empty tree
int build(int tl, int tr) {
int id = ++node_cnt;
tree[id].sum = 0;
tree[id].l = 0;
tree[id].r = 0;
if (tl != tr) {
int tm = (tl + tr) / 2;
tree[id].l = build(tl, tm);
tree[id].r = build(tm + 1, tr);
}
return id;
}
// Update: Add a student with upper bound 'pos' (B value)
int update(int prev_node, int tl, int tr, int pos) {
int id = ++node_cnt;
tree[id] = tree[prev_node];
tree[id].sum++;
if (tl == tr) return id;
int tm = (tl + tr) / 2;
if (pos <= tm)
tree[id].l = update(tree[prev_node].l, tl, tm, pos);
else
tree[id].r = update(tree[prev_node].r, tm + 1, tr, pos);
return id;
}
// Query: Count students with B in range [ql, qr]
// Since we access roots[R] - roots[L], we effectively filter by A first.
int query(int node, int tl, int tr, int ql, int qr) {
if (ql > qr) return 0;
if (ql == tl && qr == tr) return tree[node].sum;
int tm = (tl + tr) / 2;
if (qr <= tm) return query(tree[node].l, tl, tm, ql, qr);
if (ql > tm) return query(tree[node].r, tm + 1, tr, ql, qr);
return query(tree[node].l, tl, tm, ql, tm) +
query(tree[node].r, tm + 1, tr, tm + 1, qr);
}
// Counts students satisfying: min_size_pref > A_lower AND max_size_pref >= B_threshold
// This maps to: count students in PST range (A_lower, N] with value >= B_threshold
int count_students(int a_lower, int b_threshold) {
if (b_threshold > N_global) return 0;
// We want students with A in (a_lower, N_global].
// Since roots[i] accumulates 1..i, roots[N] - roots[a_lower] gives range (a_lower, N].
// Note: The problem logic often requires students with A <= K_i.
// Let's stick to the DP recurrence: count(K_j < A <= K_i, B >= K_i).
int cnt_all = query(roots[N_global], 1, N_global, b_threshold, N_global); // All with B >= K_i
int cnt_low = query(roots[a_lower], 1, N_global, b_threshold, N_global); // Those with A <= K_j
// This function returns students with A > a_lower AND B >= b_threshold
// But wait, the standard reduction usually uses: count(A <= a_upper, B >= b_threshold)
// Let's adjust for the DP needs:
// We usually compute: Count(A <= K_i, B >= K_i) - Count(A <= K_j, B >= K_i)
return 0; // Placeholder, logic moved inside solve for clarity
}
// Specific helper for the DP transition
// Returns count of students with A <= a_limit AND B >= b_limit
int get_cnt(int a_limit, int b_limit) {
if (b_limit > N_global) return 0;
return query(roots[a_limit], 1, N_global, b_limit, N_global);
}
void init(int N, int A[], int B[]) {
N_global = N;
node_cnt = 0;
vector<vector<int>> by_A(N + 1);
for (int i = 0; i < N; i++) {
by_A[A[i]].push_back(B[i]);
}
roots[0] = build(1, N);
for (int i = 1; i <= N; i++) {
roots[i] = roots[i-1];
for (int b_val : by_A[i]) {
roots[i] = update(roots[i], 1, N, b_val);
}
}
}
struct StackItem {
int idx; // Index j
int limit_y; // The K value up to which this j is optimal
};
int can(int M, int K[]) {
// Sort K to apply Hall's on intervals
vector<int> k_sorted(M + 1);
k_sorted[0] = 0;
for (int i = 0; i < M; i++) k_sorted[i+1] = K[i];
sort(k_sorted.begin() + 1, k_sorted.end());
vector<long long> dp(M + 1); // dp[i] = max slack after satisfying 1..i
dp[0] = 0;
vector<StackItem> st;
st.push_back({0, N_global + 1});
for (int i = 1; i <= M; i++) {
int k_curr = k_sorted[i];
// 1. Maintain Convex Hull (Find best j)
// We pop if the current requested size k_curr exceeds the validity of the top strategy
while (st.size() > 1 && st.back().limit_y <= k_curr) {
st.pop_back();
}
int j = st.back().idx;
// 2. DP Recurrence
// Slack[i] = Slack[j] + (Supply between j and i) - Demand[i]
// Supply = Students with K[j] < A <= K[i] AND B >= K[i]
// Calculated as: Count(A <= K[i], B >= K[i]) - Count(A <= K[j], B >= K[i])
int count_upto_i = get_cnt(k_curr, k_curr);
int count_upto_j = get_cnt(k_sorted[j], k_curr);
dp[i] = dp[j] + (count_upto_i - count_upto_j) - k_curr;
if (dp[i] < 0) return 0; // Hall's condition violated
// 3. Update Convex Hull (Add i)
// We need to find the split point 'ans' (a value of team size Y)
// where strategy 'i' becomes worse than 'st.back()'.
// Equation: dp[i] + Count(A<=Y, B>=Y) - Count(A<=K[i], B>=Y) >= dp[old] + Count(A<=Y, B>=Y) - Count(A<=K[old], B>=Y)
// Simplifies to: dp[i] - Count(A<=K[i], B>=Y) >= dp[old] - Count(A<=K[old], B>=Y)
// -> Count(A<=K[i], B>=Y) - Count(A<=K[old], B>=Y) <= dp[i] - dp[old]
// LHS is monotonically non-increasing as Y increases (fewer students have B >= large Y)
while (true) {
int old_idx = st.back().idx;
long long diff_dp = dp[i] - dp[old_idx];
// Binary Search for the split point
int low = k_curr + 1;
int high = N_global + 1;
int ans = N_global + 1;
while (low <= high) {
int mid = (low + high) / 2;
// Cost function difference
int val = get_cnt(k_curr, mid) - get_cnt(k_sorted[old_idx], mid);
if (val <= diff_dp) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
if (ans >= st.back().limit_y) {
st.pop_back();
if (st.empty()) {
st.push_back({i, N_global + 1});
break;
}
} else {
st.push_back({i, ans});
break;
}
}
}
return 1;
}
