#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
int n = int(p.size());
vector<vector<int>> at(5);
vector<int> c(5);
for (int i = 0; i < n; i++) {
at[t[i]].push_back(i);
c[t[i]] += 1;
}
for (int i = 1; i <= 4; i++) {
sort(at[i].begin(), at[i].end(), [&](int x, int y) {
return p[x] < p[y];
});
}
auto Check = [&](vector<int> ids) {
int64_t cur = A;
int n = int(ids.size());
vector<bool> was(n);
vector<int> order;
for (int it = 0; it < n; it++) {
cur = min(cur, int64_t(1e17));
int64_t best = -1;
int id = -1;
for (int i = 0; i < n; i++) {
if (was[i] || cur < p[ids[i]]) {
continue;
}
int64_t new_a = (cur - p[ids[i]]) * t[ids[i]];
if (new_a >= best) {
best = new_a;
id = i;
}
}
if (id != -1) {
was[id] = true;
order.push_back(ids[id]);
cur = best;
} else {
return vector<int>();
}
}
return order;
};
vector<int> res;
for (int i1 = 0; i1 <= c[1]; i1++) {
for (int i2 = 0; i2 <= c[2]; i2++) {
for (int i3 = 0; i3 <= c[3]; i3++) {
for (int i4 = 0; i4 <= c[4]; i4++) {
vector<int> ids;
for (int i = 0; i < i4; i++) {
ids.push_back(at[4][i]);
}
for (int i = 0; i < i3; i++) {
ids.push_back(at[3][i]);
}
for (int i = 0; i < i2; i++) {
ids.push_back(at[2][i]);
}
for (int i = 0; i < i1; i++) {
ids.push_back(at[1][i]);
}
ids = Check(ids);
if (int(ids.size()) > int(res.size())) {
res = ids;
}
}
}
}
}
return res;
}
