#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool comp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
return (long long)a.second.first * a.second.second * b.second.second + (long long)b.second.first * b.second.second <
(long long)b.second.first * a.second.second * b.second.second + (long long)a.second.first * a.second.second;
}
std::vector<signed> max_coupons(signed A, std::vector<signed> P, std::vector<signed> T) {
vector<vector<pair<int, int>>> vals(4, vector<pair<int, int>>());
for (int i = 0; i < P.size(); i++) {
vals[T[i] - 1].push_back({ P[i], i });
}
vals[0].push_back({ 0, -1 });
for (int i = 0; i < 4; i++) sort(vals[i].begin(), vals[i].end());
for (int i = 1; i < vals[0].size(); i++) vals[0][i].first += vals[0][i - 1].first;
vector<signed> vans;
int ans = 0;
for (int i = 0; i <= vals[1].size(); i++) {
for (int j = 0; j <= vals[2].size(); j++) {
for (int k = 0; k <= vals[3].size(); k++) {
vector<pair<int, pair<int, int>>> valss;
for (int l = 0; l < i; l++) valss.push_back({ vals[1][l].second, {vals[1][l].first, 2} });
for (int l = 0; l < j; l++) valss.push_back({ vals[2][l].second, {vals[2][l].first, 3} });
for (int l = 0; l < k; l++) valss.push_back({ vals[3][l].second, {vals[3][l].first, 4} });
sort(valss.begin(), valss.end(), comp);
int _A = A;
int nans = 0, bestI = 0;
for (int l = 0; l <= valss.size(); l++) {
auto iter = upper_bound(vals[0].begin(), vals[0].end(), make_pair(_A, (int)INT_MAX));
iter--;
if (nans < l + (iter - vals[0].begin())) {
nans = l + (iter - vals[0].begin());
bestI = l;
}
if (l != valss.size()) _A = valss[l].second.second * (_A - valss[l].second.first);
if (_A > 1000000000000000 && i + j + k + vals[0].size() > ans) {
vans.clear();
ans = i + j + k + vals[0].size();
for (int m = 0; m < valss.size(); m++) vans.push_back(valss[m].first);
for (int m = 1; m < vals[0].size(); m++) vans.push_back(vals[0][m].second);
break;
}
if (_A < 0) break;
}
if (ans < nans) {
vans.clear();
ans = nans;
for (int l = 0; l < bestI; l++) vans.push_back(valss[l].first);
for (int l = bestI; l < ans; l++) vans.push_back(vals[0][l + 1 - bestI].second);
}
}
}
}
return vans;
}
