#pragma GCC optimize("trapv")
#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) {
i64 sum = 0;
array<vector<pair<int, int>>, 5> things;
for (int i = 0; i < P.size(); i++) {
things[T[i]].push_back({P[i], i});
sum += P[i];
}
for (auto &x: things)
sort(x.begin(), x.end());
vector<i64> t1_ps = {0};
for (auto x: things[1])
t1_ps.push_back(t1_ps.back() + x.first);
i64 rem = A;
pair<int, int> best = {upper_bound(t1_ps.begin(), t1_ps.end(), rem) - t1_ps.begin() - 1, 0};
for (int i = 0; i < things[2].size(); i++) {
rem = (rem - things[2][i].first) * 2;
if (rem >= sum) {
vector<int> ans;
for (auto x: things[2]) ans.push_back(x.second);
for (auto x: things[1]) ans.push_back(x.second);
return ans;
}
if (rem < 0) break;
best = max(best, {i + 1 + upper_bound(t1_ps.begin(), t1_ps.end(), rem) - t1_ps.begin() - 1, i + 1});
}
vector<int> ans;
for (int i = 0; i < best.second; i++) ans.push_back(things[2][i].second);
while (ans.size() < best.first) ans.push_back(things[1][ans.size() - best.second].second);
return ans;
}
