#include <bits/stdc++.h>
#include "jelly.h"
using namespace std;
// testuje cos tylko i tak to juz wbilem
int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
int n = (int)a.size();
// items: (b_i, a_i) - sortujemy po cenie w sklepie B
vector<pair<int,int>> items(n);
for (int i = 0; i < n; i++) {
items[i] = {b[i], a[i]};
}
sort(items.begin(), items.end());
// preB[k] = koszt kupienia pierwszych k elementów w sklepie B
vector<long long> preB(n + 1, 0);
for (int i = 0; i < n; i++) {
preB[i + 1] = preB[i] + items[i].first;
}
const int INF = 1e9;
// dp[c] = minimalny koszt w sklepie A, aby kupić dokładnie c smaków z aktualnego sufiksu
vector<int> dp(n + 1, INF);
dp[0] = 0;
// max_items[k] = maksymalna liczba smaków z items[k:] możliwa do kupienia w sklepie A za budżet x
vector<int> max_items(n + 1, 0);
max_items[n] = 0;
// Przetwarzamy od końca: dla każdego k chcemy znać "ile da się wziąć z sufiksu w A"
for (int j = n - 1; j >= 0; j--) {
int a_val = items[j].second;
// 0/1 knapsack - aktualizacja dp wstecz
for (int c = n; c >= 1; c--) {
if (dp[c - 1] != INF) {
dp[c] = min(dp[c], dp[c - 1] + a_val);
}
}
// wyznacz maksymalną liczbę elementów z sufiksu [j..n-1], którą da się kupić w A
int max_c = 0;
int limit = n - j;
for (int c = 0; c <= limit; c++) {
if (dp[c] <= x) max_c = c;
}
max_items[j] = max_c;
}
// Próbujemy wszystkich podziałów:
// - pierwsze k (najtańsze w B) kupujemy w B
// - resztę wybieramy optymalnie w A z sufiksu items[k:]
int ans = 0;
for (int k = 0; k <= n; k++) {
if (preB[k] <= (long long)y) {
ans = max(ans, k + max_items[k]);
}
}
return ans;
}
