#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = P.size();
// BFS state: current tokens + bitmask of used coupons (we'll optimize later)
struct State {
long long tokens;
vector<int> seq;
vector<bool> used;
};
queue<State> q;
unordered_map<long long, int> best; // tokens -> max coupons
vector<bool> used(N, false);
q.push({A, {}, used});
best[A] = 0;
vector<int> answer;
while (!q.empty()) {
State cur = q.front(); q.pop();
if ((int)cur.seq.size() > (int)answer.size())
answer = cur.seq;
for (int i = 0; i < N; i++) {
if (cur.used[i]) continue;
if (cur.tokens < P[i]) continue;
long long new_tokens = (cur.tokens - P[i]) * T[i];
// prune worse states
if (best.count(new_tokens) && best[new_tokens] >= (int)cur.seq.size() + 1)
continue;
best[new_tokens] = cur.seq.size() + 1;
State nxt = cur;
nxt.tokens = new_tokens;
nxt.used[i] = true;
nxt.seq.push_back(i);
q.push(nxt);
}
}
return answer;
}
