#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 dp_n_to_power_of_3() {
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(x+1, vector<int>(y+1, 0)));
int max_res = 0;
for (int i=1; i<=n; i++) {
for (int X=0; X<=x; X++) {
for (int Y=0; Y<=y; Y++) {
dp[i][X][Y] = dp[i-1][X][Y];
int ai = a[i-1], bi = b[i-1];
if (X >= ai) dp[i][X][Y] = max(dp[i][X][Y], dp[i-1][X-ai][Y]+1);
if (Y >= bi) dp[i][X][Y] = max(dp[i][X][Y], dp[i-1][X][Y-bi]+1);
max_res = max(max_res, dp[i][X][Y]);
}
}
}
return max_res;
}
int brute_y_equals_to_0() {
priority_queue<int> Q; // < -a[i] >
int res = 0;
for (int i=0; i<n; i++) {
if (b[i] == 0) {
res++;
continue;
}
Q.push(-a[i]);
}
int budget = x;
while (!Q.empty()) {
int ai = -Q.top(); Q.pop();
if (budget - ai >= 0) {
budget -= ai;
res++;
}
else break;
}
return res;
}
int heura_bi_equalst_to_bj() {
priority_queue<int> Q; // < -a[i] >
for (int i=0; i<n; i++) Q.push(-a[i]);
int res = 0;
int budget = x;
while (!Q.empty()) {
int ai = -Q.top(); 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 heura_ai_equals_to_bi() {
if (y > x) {
swap(x, y);
swap(a, b);
}
priority_queue<int> Q;
for (int i=0; i<n; i++) Q.push(-a[i]);
int budget = x;
vector<int> chosen;
multiset<int> chosen_X;
multiset<int> chosen_Y;
int sum_of_chosen = 0;
while (!Q.empty()) {
int ai = -Q.top(); Q.pop();
if (budget - ai >= 0) {
budget -= ai;
chosen.push_back(ai);
chosen_X.insert(ai);
sum_of_chosen += ai;
}
else {
Q.push(-ai);
break;
}
}
int rest_x = budget;
budget = y;
while (!Q.empty()) {
int ai = -Q.top(); Q.pop();
if (budget - ai >= 0) {
budget -= ai;
chosen.push_back(ai);
chosen_Y.insert(ai);
sum_of_chosen += ai;
}
else {
Q.push(-ai);
break;
}
}
int rest_y = budget;
int rest = rest_x + rest_y;
if (Q.empty() || -Q.top() > rest || rest_x == 0 || rest_y == 0) return ssize(chosen);
int candidate = -Q.top();
// cout << "rest_x = " << rest_x << ", rest_y = " << rest_y << endl;
// cout << "candidate = " << candidate << endl;
auto it = chosen_X.lower_bound(candidate - rest_x);
// cout << "do wywalenia z X: " << *it << endl;
if (it != chosen_X.end() && *it <= rest_y) return ssize(chosen) + 1;
it = chosen_Y.lower_bound(candidate - rest_y);
// cout << "do wywalenia z Y: " << *it << endl;
if (it != chosen_Y.end() && *it <= rest_x) return ssize(chosen) + 1;
return -1;
}
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();
if (x <= 500 && y <= 500 && n <= 200) return dp_n_to_power_of_3();
if (ai_equals_to_bi) return heura_ai_equals_to_bi();
return 0;
}
