#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Item {
ll P;
int T;
int id;
};
// min-heap by price within a fixed T (since K is monotone in P when T fixed)
template<class Tpair>
using MinHeap = priority_queue<Tpair, vector<Tpair>, greater<Tpair>>;
static inline bool lessK(ll P1, int T1, ll P2, int T2) {
// compare P1*T1/(T1-1) < P2*T2/(T2-1) without floating
// i.e. P1*T1*(T2-1) < P2*T2*(T1-1)
// T in {2,3,4}, (T-1)>0
__int128 lhs = (__int128)P1 * T1 * (T2 - 1);
__int128 rhs = (__int128)P2 * T2 * (T1 - 1);
if (lhs != rhs) return lhs < rhs;
// tie-break: prefer larger multiplier to boost future capacity
return T1 > T2;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
const ll INF = (ll)4e18; // cap to prevent overflow
int N = (int)P.size();
// Split into T==1 and T>1 buckets, each store (P, id)
vector<pair<ll,int>> ones;
array<vector<pair<ll,int>>, 5> bucket; // bucket[2], bucket[3], bucket[4]
for (int i = 0; i < N; ++i) {
if (T[i] == 1) ones.emplace_back((ll)P[i], i);
else bucket[T[i]].emplace_back((ll)P[i], i);
}
// Sort each by price ascending (we'll push into heaps when price <= X)
sort(ones.begin(), ones.end());
for (int t : {2,3,4}) sort(bucket[t].begin(), bucket[t].end());
// Pointers per bucket to stream-in affordable items
array<int, 5> ptr{}; // default 0
// Available heaps: per T, heap of (P, id)
MinHeap<pair<ll,int>> avail2, avail3, avail4;
auto push_affordable = [&](ll X) {
// move items with P <= X into avail heaps
for (int t : {2,3,4}) {
auto &vec = bucket[t];
int &j = ptr[t];
while (j < (int)vec.size() && vec[j].first <= X) {
if (t == 2) avail2.push(vec[j]);
else if (t == 3) avail3.push(vec[j]);
else avail4.push(vec[j]);
++j;
}
}
};
ll X = A;
push_affordable(X);
// Record the dynamic path of T>1 choices so we can later choose best prefix
struct Step { int id; ll P; int T; ll afterX; };
vector<Step> path;
// Greedy loop among T>1: at each step pick the affordable item with minimal K across {2,3,4} heap tops
while (true) {
// pick candidate tops (must check affordable at *current* X)
bool has2 = !avail2.empty() && avail2.top().first <= X;
bool has3 = !avail3.empty() && avail3.top().first <= X;
bool has4 = !avail4.empty() && avail4.top().first <= X;
if (!has2 && !has3 && !has4) break;
// choose by minimal K; ties prefer larger T
ll cP = -1; int cT = -1; int cid = -1;
auto consider = [&](ll p, int t, int id){
if (cT == -1 || lessK(p,t,cP,cT)) { cP=p; cT=t; cid=id; }
};
if (has2) consider(avail2.top().first, 2, avail2.top().second);
if (has3) consider(avail3.top().first, 3, avail3.top().second);
if (has4) consider(avail4.top().first, 4, avail4.top().second);
// pop chosen from its heap
if (cT == 2) avail2.pop();
else if (cT == 3) avail3.pop();
else avail4.pop();
// buy it
if (X < cP) break; // shouldn't happen due to has* checks
ll NX = X - cP;
// multiply with cap
if (NX > 0 && cT > 1) {
__int128 tmp = (__int128)NX * cT;
NX = (tmp > INF ? INF : (ll)tmp);
} else {
NX = NX * cT; // could be 0
}
X = NX;
path.push_back({cid, cP, cT, X});
// newly affordable items may appear
push_affordable(X);
}
// Pre-compute, for each prefix length r, total count = r + (#ones affordable from X_r)
// First consider r=0 (no T>1)
auto count_ones_from = [&](ll x)->int{
int cnt = 0;
for (auto &pr : ones) {
if (x >= pr.first) { x -= pr.first; ++cnt; }
else break;
}
return cnt;
};
int best_r = 0;
ll curX = A;
int best_total = count_ones_from(curX);
for (int r = 1; r <= (int)path.size(); ++r) {
ll xr = path[r-1].afterX;
int total = r + count_ones_from(xr);
if (total > best_total) {
best_total = total;
best_r = r;
}
}
// Reconstruct answer order: take first best_r steps from path, then eat ones greedily
vector<int> ans;
ans.reserve(best_total);
ll x2 = A;
for (int i = 0; i < best_r; ++i) {
auto [id, p, t, afterX] = path[i];
ans.push_back(id);
// forward-simulate X to align
ll NX = x2 - p;
if (NX > 0 && t > 1) {
__int128 tmp = (__int128)NX * t;
NX = (tmp > INF ? INF : (ll)tmp);
} else {
NX = NX * t;
}
x2 = NX;
}
for (auto &pr : ones) {
if (x2 >= pr.first) {
x2 -= pr.first;
ans.push_back(pr.second);
} else break;
}
return ans;
}
