#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = P.size();
vector<int> type1, type234;
for (int i = 0; i < N; i++) {
if (T[i] == 1) type1.push_back(i);
else type234.push_back(i);
}
sort(type234.begin(), type234.end(), [&](int i, int j) {
if (P[i] != P[j]) return P[i] < P[j];
return T[i] > T[j];
});
vector<int> result;
long long tokens = A;
for (int idx : type234) {
if (tokens >= P[idx]) {
tokens = (tokens - P[idx]) * T[idx];
result.push_back(idx);
}
}
sort(type1.begin(), type1.end(), [&](int i, int j) {
return P[i] < P[j];
});
for (int idx : type1) {
if (tokens >= P[idx]) {
tokens = tokens - P[idx];
result.push_back(idx);
}
}
return result;
}
