#include <bits/stdc++.h>
using namespace std;
// Using a struct makes the DP table much easier to read than using std::pair
struct Result {
int spentA; // Minimum money spent in Store A
int flavorCount; // Maximum unique flavors collected
};
struct Jelly {
int costA;
int costB;
};
// Comparator to sort jellies by their price in Store A
bool compareByStoreA(const Jelly &a, const Jelly &b) {
return a.costA < b.costA;
}
int find_maximum_unique(int budgetA, int budgetB, vector<int> a, vector<int> b) {
int n = a.size();
vector<Jelly> jellies(n);
for (int i = 0; i < n; i++) {
jellies[i] = {a[i], b[i]};
}
// Step 1: Sort by Store A costs (Greedy strategy)
sort(jellies.begin(), jellies.end(), compareByStoreA);
// Step 2: DP Table
// dp[i][j] = best result considering first 'i' jellies with 'j' spent in Store B
vector<vector<Result>> dp(n + 1, vector<Result>(budgetB + 1));
// Initialize the base case
dp[0][0] = {0, 0};
for (int i = 1; i <= n; i++) {
int currentA = jellies[i - 1].costA;
int currentB = jellies[i - 1].costB;
for (int j = 0; j <= budgetB; j++) {
// OPTION 1: Don't buy jelly 'i' at all
// Start by assuming the best we can do is what we did for 'i-1'
dp[i][j] = dp[i - 1][j];
// OPTION 2: Buy jelly 'i' from Store A
// We only do this if it's affordable and improves our flavor count
if (dp[i - 1][j].spentA + currentA <= budgetA) {
int newSpentA = dp[i - 1][j].spentA + currentA;
int newFlavors = dp[i - 1][j].flavorCount + 1;
// If this option gives more flavors, update
if (newFlavors > dp[i][j].flavorCount) {
dp[i][j] = {newSpentA, newFlavors};
}
}
// OPTION 3: Buy jelly 'i' from Store B
if (j >= currentB) {
int prevSpentA = dp[i - 1][j - currentB].spentA;
int prevFlavors = dp[i - 1][j - currentB].flavorCount;
int newFlavors = prevFlavors + 1;
// Update if we find a strictly better flavor count
if (newFlavors > dp[i][j].flavorCount) {
dp[i][j] = {prevSpentA, newFlavors};
}
// If flavor count is tied, keep the one that saves more money in Store A
else if (newFlavors == dp[i][j].flavorCount) {
dp[i][j].spentA = min(dp[i][j].spentA, prevSpentA);
}
}
}
}
// The answer is the maximum flavors found using any amount of budget B
int maxTotalFlavors = 0;
for (int j = 0; j <= budgetB; j++) {
maxTotalFlavors = max(maxTotalFlavors, dp[n][j].flavorCount);
}
return maxTotalFlavors;
}
