#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
const long long CLAMP = (1LL<<62); // keep X bounded to avoid overflow
int N = (int)P.size();
// Group by type; store (price, index) and sort by price asc.
vector<pair<int,int>> by[5];
for (int i = 0; i < N; ++i) by[T[i]].push_back({P[i], i});
for (int t = 1; t <= 4; ++t) sort(by[t].begin(), by[t].end());
// Current tokens (use long long; compute transitions in __int128 to be safe)
long long X = A;
vector<int> ans;
// Pointers to the next not-yet-bought coupon in each multiplier bucket
size_t p2 = 0, p3 = 0, p4 = 0;
auto next_tokens = [](long long X, int price, int t) -> __int128 {
return (__int128)(X - price) * t;
};
// Phase 1: use multipliers greedily
while (true) {
int bestT = 0, bestPrice = 0, bestIdx = -1;
__int128 bestVal = -1;
if (p2 < by[2].size() && by[2][p2].first <= X) {
auto val = next_tokens(X, by[2][p2].first, 2);
if (val > bestVal) { bestVal = val; bestT = 2; bestPrice = by[2][p2].first; bestIdx = by[2][p2].second; }
}
if (p3 < by[3].size() && by[3][p3].first <= X) {
auto val = next_tokens(X, by[3][p3].first, 3);
if (val > bestVal) { bestVal = val; bestT = 3; bestPrice = by[3][p3].first; bestIdx = by[3][p3].second; }
}
if (p4 < by[4].size() && by[4][p4].first <= X) {
auto val = next_tokens(X, by[4][p4].first, 4);
if (val > bestVal) { bestVal = val; bestT = 4; bestPrice = by[4][p4].first; bestIdx = by[4][p4].second; }
}
if (bestT == 0) break; // no multiplier affordable
// Buy it
ans.push_back(bestIdx);
__int128 nxt = bestVal;
if (nxt > (__int128)CLAMP) X = CLAMP; // clamp to avoid overflow on future ops
else if (nxt < 0) X = -1; // (won't happen since price<=X)
else X = (long long)nxt;
if (bestT == 2) ++p2;
else if (bestT == 3) ++p3;
else ++p4;
}
// Phase 2: spend remaining tokens on T=1, cheapest-first
size_t p1 = 0;
while (p1 < by[1].size() && by[1][p1].first <= X) {
X -= by[1][p1].first;
ans.push_back(by[1][p1].second);
++p1;
}
return ans;
}
