#include <bits/stdc++.h>
#include "jelly.h"
using namespace std;
// n <= 2000, x,y <= 10000, a_i, b_i <= 10000
static inline int suffix_max_count(const vector<int>& freqA, int budget) {
int cnt = 0;
int rem = budget;
// cost 0: take all free items
cnt += freqA[0];
// costs 1..10000
for (int cost = 1; cost < (int)freqA.size(); ++cost) {
int c = freqA[cost];
if (c == 0) continue;
if (rem < cost) break;
int take = min(c, rem / cost);
cnt += take;
rem -= take * cost;
if (rem < cost) break;
}
return cnt;
}
int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
int n = (int)a.size();
// items: (a_i, b_i)
vector<pair<int,int>> items(n);
for (int i = 0; i < n; ++i) items[i] = {a[i], b[i]};
// sort by b ascending
sort(items.begin(), items.end(), [](const auto& p1, const auto& p2){
if (p1.second != p2.second) return p1.second < p2.second;
return p1.first < p2.first;
});
const int MAXC = 10000;
// freqA[c] = how many items in current suffix have a = c
vector<int> freqA(MAXC + 1, 0);
for (auto [ai, bi] : items) freqA[ai]++;
// dp[c] = maximum sum of b we can "cover" using A-cost <= c (subset of prefix)
vector<int> dp(x + 1, 0);
long long prefixB = 0; // sum of b in first t items
int best = 0;
for (int t = 0; t <= n; ++t) {
// need to cover excess = max(0, prefixB - y)
long long excess_ll = prefixB - (long long)y;
int excess = (excess_ll > 0 ? (int)excess_ll : 0);
if (dp[x] >= excess) {
// find minimal c such that dp[c] >= excess
int c_min = 0;
while (c_min <= x && dp[c_min] < excess) ++c_min;
if (c_min <= x) {
int rem_budget = x - c_min;
int extra = suffix_max_count(freqA, rem_budget);
best = max(best, t + extra);
}
}
if (t == n) break;
// move item t from suffix to prefix
int ai = items[t].first;
int bi = items[t].second;
freqA[ai]--;
prefixB += bi;
// update knapsack with (weight=ai, value=bi)
if (ai == 0) {
for (int c = 0; c <= x; ++c) dp[c] += bi;
} else if (ai <= x) {
for (int c = x; c >= ai; --c) {
int cand = dp[c - ai] + bi;
if (cand > dp[c]) dp[c] = cand;
}
}
}
return best;
}
