#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
typedef long long i64;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
array<vector<int>, 5> things;
for (int i = 0; i < P.size(); i++)
things[T[i]].push_back(P[i]);
for (auto &x: things)
sort(things.begin(), things.end());
vector<i64> t1_ps = {0};
for (auto x: things[1])
t1_ps.push_back(t1_ps.back() + x);
i64 rem = A;
pair<int, int> best = {upper_bound(t1_ps.begin(), t1_ps.end(), A) - t1_ps.begin() - 1, 0};
for (int i = 0; i < things[2].size(); i++) {
A = (A - things[2][i]) * 2;
if (A < 0) break;
best = max(best, {i + 1 + upper_bound(t1_ps.begin(), t1_ps.end(), A) - t1_ps.begin() - 1, i + 1});
}
vector<int> ans;
for (int i = 0; i < best.second; i++) ans.push_back(things[2][i]);
while (ans.size() < best.first) ans.push_back(things[1][ans.size() - best.second]);
return ans;
}
