#include <vector>
#include <algorithm>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
using ll = long long;
const int n = (int)P.size();
// Bucket coupons by multiplier T in {1,2,3,4}, keep (price, index)
vector<pair<ll,int>> buckets[5];
for (int i = 0; i < n; ++i) {
int t = T[i];
if (t < 1) t = 1;
if (t > 4) t = 4;
buckets[t].push_back({(ll)P[i], i});
}
// Sort each bucket by price ascending (tie-break by index for determinism)
for (int t = 1; t <= 4; ++t) {
sort(buckets[t].begin(), buckets[t].end(),
[](const pair<ll,int>& a, const pair<ll,int>& b){
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
}
// Pointers to the "cheapest remaining" in each bucket
size_t ptr[5] = {0,0,0,0,0};
auto has = [&](int t)->bool { return ptr[t] < buckets[t].size(); };
auto ceil_div = [](ll x, int t)->ll { return (x + t - 1) / t; };
ll R = 0; // current "required tokens" for the already-built suffix
vector<int> last_to_first; // we append items as the LAST element each step
while (true) {
ll best_cost = (1LL<<62);
int best_t = -1;
// Among T=1..4, consider the cheapest remaining in each bucket
for (int t = 1; t <= 4; ++t) if (has(t)) {
ll p = buckets[t][ptr[t]].first;
ll c = p + ceil_div(R, t); // cost_t(R) = P + ceil(R / T)
// tie-break: prefer larger T (helps future division), then smaller index
if (c < best_cost || (c == best_cost && t > best_t)) {
best_cost = c;
best_t = t;
}
}
if (best_t == -1) break; // nothing left
if (best_cost > (ll)A) break; // cannot extend without exceeding A
// Accept this as the last element of the sequence
last_to_first.push_back(buckets[best_t][ptr[best_t]].second);
++ptr[best_t];
R = best_cost; // new requirement for the enlarged suffix
}
// The forward buying order is the reverse of the "last-to-first" list
reverse(last_to_first.begin(), last_to_first.end());
return last_to_first;
}
