#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
int n; // liczba produktów w każdym ze sklepów
int x; // pieniądze do wydania w sklepie A
int y; // pieniądze do wydania w sklepie B
vector<int> a; // ceny produktów w sklepie A
vector<int> b; // ceny produktów w sklepie B
int calc_res(int m) {
int sum_x = 0, sum_y = 0, cnt_diff = 0;
for (int i=0; i<n; i++) {
bool temp = false;
if (m & (1 << i)) {
sum_x += a[i];
temp = true;
}
if (m & (1 << (i+n))) {
sum_y += b[i];
temp = true;
}
if (temp) cnt_diff++;
}
if (sum_x > x || sum_y > y) return 0;
return cnt_diff;
}
int brute_exp() {
int max_res = 0;
for (int i=0; i<(1<<(2*n)); i++) {
max_res = max(max_res, calc_res(i));
}
return max_res;
}
int brute_y_equals_to_0() {
sort(a.begin(), a.end());
int res = 0;
int budget = x;
for (int i=0; i<n; i++) {
if (budget - a[i] >= 0) {
budget -= a[i];
res++;
}
}
return res;
}
int heura_bi_equalst_to_bj() {
priority_queue<pair<int, int>> Q; // < -a[i], i >
vector<bool> already_bought(n, false);
for (int i=0; i<n; i++) Q.push({ -a[i], i });
int res = 0;
int budget = x;
while (!Q.empty()) {
int ai = -Q.top().first;
int i = Q.top().second;
Q.pop();
if (budget - ai >= 0) {
budget -= ai;
res++;
}
else {
break;
}
}
int max_bought_in_b = (b[0] != 0) ? y / b[0] : n;
return min(n, res + max_bought_in_b);
}
int find_maximum_unique(int _x, int _y, std::vector<int> _a, std::vector<int> _b) {
n = _a.size();
x = _x;
y = _y;
a = _a;
b = _b;
if (x <= 500 && y <= 500 && n <= 12) return brute_exp();
if (y == 0) return brute_y_equals_to_0();
bool bi_equals_to_bj = true;
bool ai_equals_to_bi = true;
int bj = b[0];
for (int i=0; i<n; i++) {
if (b[i] != bj) {
bi_equals_to_bj = false;
if (!ai_equals_to_bi) break;
}
if (a[i] != b[i]) {
ai_equals_to_bi = false;
if (!bi_equals_to_bj) break;
}
}
if (bi_equals_to_bj) return heura_bi_equalst_to_bj();
return 0;
}
