#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 CLAMP = (1LL<<62); // cap to avoid overflow
int N = (int)P.size();
// Group coupons by type
vector<pair<int,int>> by[5];
for (int i = 0; i < N; ++i) {
by[T[i]].push_back({P[i], i});
}
// Sort each group ascending by price
for (int t = 1; t <= 4; ++t)
sort(by[t].begin(), by[t].end());
// Current tokens
ll X = A;
vector<int> ans;
// Pointers to cheapest not-yet-used coupon of each multiplier type
size_t p2 = 0, p3 = 0, p4 = 0;
// Phase 1: Buy multipliers greedily by cheapest affordable
while (true) {
int chosenType = 0;
int chosenIdx = -1;
int chosenPrice = 0;
// Among available coupons, choose the cheapest affordable one
int minPrice = INT_MAX;
if (p2 < by[2].size() && by[2][p2].first <= X && by[2][p2].first < minPrice) {
minPrice = by[2][p2].first;
chosenType = 2; chosenPrice = by[2][p2].first; chosenIdx = by[2][p2].second;
}
if (p3 < by[3].size() && by[3][p3].first <= X && by[3][p3].first < minPrice) {
minPrice = by[3][p3].first;
chosenType = 3; chosenPrice = by[3][p3].first; chosenIdx = by[3][p3].second;
}
if (p4 < by[4].size() && by[4][p4].first <= X && by[4][p4].first < minPrice) {
minPrice = by[4][p4].first;
chosenType = 4; chosenPrice = by[4][p4].first; chosenIdx = by[4][p4].second;
}
if (chosenType == 0) break; // none affordable
// Buy it
ans.push_back(chosenIdx);
__int128 nxt = (__int128)(X - chosenPrice) * chosenType;
if (nxt > CLAMP) X = CLAMP;
else X = (ll)nxt;
if (chosenType == 2) ++p2;
else if (chosenType == 3) ++p3;
else ++p4;
}
// Phase 2: Spend remaining tokens on T=1 cheapest-first
sort(by[1].begin(), by[1].end());
for (auto &c : by[1]) {
if (c.first <= X) {
X -= c.first;
ans.push_back(c.second);
} else break;
}
return ans;
}
