#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
using ll = long long;
const ll BIG = 2000000000LL; // 2e9 threshold described above
int N = (int)P.size();
array<vector<pair<int,int>>, 5> byT; // byT[t] holds {P, idx}
for (int i = 0; i < N; ++i) {
int t = T[i];
if (t < 1 || t > 4) continue; // defensive
byT[t].push_back({P[i], i});
}
for (int t = 1; t <= 4; ++t) {
sort(byT[t].begin(), byT[t].end()); // sort by price ascending
}
array<int, 5> ptr{}; // next unused per T
vector<int> order;
order.reserve(N);
auto affordable = [&](int t, ll x) -> bool {
return ptr[t] < (int)byT[t].size() && (ll)byT[t][ptr[t]].first <= x;
};
ll x = (ll)A;
// Main greedy loop
while (true) {
if (x >= BIG) break;
ll bestVal = -1;
int bestT = -1;
int bestIdx = -1;
int bestPrice = -1;
for (int t = 1; t <= 4; ++t) {
if (!affordable(t, x)) continue;
int price = byT[t][ptr[t]].first;
int idx = byT[t][ptr[t]].second;
// candidate next tokens; safe since x < 2e9 here
ll val = (ll)t * (x - (ll)price);
// tie-break: larger val, then larger T, then smaller price, then smaller idx
if (val > bestVal ||
(val == bestVal && t > bestT) ||
(val == bestVal && t == bestT && price < bestPrice) ||
(val == bestVal && t == bestT && price == bestPrice && idx < bestIdx)) {
bestVal = val;
bestT = t;
bestIdx = idx;
bestPrice = price;
}
}
if (bestT == -1) {
// nothing affordable in any group
return order;
}
// take it
order.push_back(bestIdx);
++ptr[bestT];
ll nextX = bestVal;
if (nextX >= BIG) {
x = BIG;
break;
} else {
x = nextX;
}
}
// If we reached BIG, we can finish deterministically:
if (x >= BIG) {
// All remaining T>1 coupons are affordable and non-decreasing
for (int t = 4; t >= 2; --t) {
for (int k = ptr[t]; k < (int)byT[t].size(); ++k) {
order.push_back(byT[t][k].second);
}
ptr[t] = (int)byT[t].size();
}
// Then all T=1 by price ascending
for (int k = ptr[1]; k < (int)byT[1].size(); ++k) {
order.push_back(byT[1][k].second);
}
ptr[1] = (int)byT[1].size();
return order;
}
// Otherwise (no affordable coupons), we’re done
return order;
}
