#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> result;
long long tokens = A;
vector<int> used(N, 0);
// Growth coupons (T >= 2)
vector<int> growth;
// Drain coupons (T == 1)
vector<int> drain;
for (int i = 0; i < N; i++) {
if (T[i] >= 2) growth.push_back(i);
else drain.push_back(i);
}
// Sort growth by price ascending, then T descending
sort(growth.begin(), growth.end(), [&](int a, int b) {
if (P[a] != P[b]) return P[a] < P[b];
return T[a] > T[b];
});
// Phase 1: growth
bool progress = true;
while (progress) {
progress = false;
for (int i : growth) {
if (used[i]) continue;
if (tokens >= P[i]) {
tokens = (tokens - P[i]) * T[i];
used[i] = 1;
result.push_back(i);
progress = true;
}
}
}
// Phase 2: drain
sort(drain.begin(), drain.end(), [&](int a, int b) {
return P[a] < P[b];
});
for (int i : drain) {
if (tokens >= P[i]) {
tokens -= P[i];
result.push_back(i);
}
}
// Remaining unused growth coupons (no longer help, treat as drain)
vector<int> leftover;
for (int i : growth)
if (!used[i]) leftover.push_back(i);
sort(leftover.begin(), leftover.end(), [&](int a, int b) {
return P[a] < P[b];
});
for (int i : leftover) {
if (tokens >= P[i]) {
tokens = (tokens - P[i]) * T[i];
result.push_back(i);
}
}
return result;
}
