#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Coupon {
int idx;
ll P;
int T;
};
static inline ll ceil_div(ll a, ll b) {
// b > 0
return (a + b - 1) / b;
}
// Given an order, check feasibility and also return the actually buyable prefix.
static pair<int, vector<int>> simulate_forward(ll A, const vector<Coupon>& order) {
ll X = A;
vector<int> taken;
taken.reserve(order.size());
for (const auto& c : order) {
if (X < c.P) break;
X = (X - c.P) * c.T;
taken.push_back(c.idx);
}
return { (int)taken.size(), move(taken) };
}
// Core heuristic: build an order backwards minimizing the required initial tokens R at each step.
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
const int N = (int)P.size();
// 1) Buckets by T, min-heap by P within each T.
// We store {P, idx}.
array<priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>>, 5> pq;
for (int i = 0; i < N; ++i) {
int t = T[i];
if (t < 1 || t > 4) continue; // safety
pq[t].push({(ll)P[i], i});
}
// 2) Backward greedy: maintain current suffix requirement R.
ll R = 0;
vector<Coupon> built; built.reserve(N);
auto peek_val = [&](int t)->pair<ll,int> {
if (pq[t].empty()) return { (ll)4e18, -1 };
auto [p, idx] = pq[t].top();
ll val = p + ceil_div(R, (ll)t);
return { val, idx };
};
while (true) {
// Among T in {1,2,3,4}, choose the class with minimal p + ceil(R/T)
ll bestVal = (ll)4e18;
int bestT = -1;
int bestIdx = -1;
for (int t = 1; t <= 4; ++t) {
auto [val, idx] = peek_val(t);
if (val < bestVal || (val == bestVal && t > bestT)) { // tie-break: larger T first
bestVal = val;
bestT = t;
bestIdx = idx;
}
}
if (bestIdx == -1) break;
if (bestVal > (ll)A) break; // cannot extend while keeping requirement <= A
// Take it into the backward-built suffix
auto [p, idx] = pq[bestT].top(); pq[bestT].pop();
built.push_back(Coupon{ idx, p, bestT });
R = bestVal; // new requirement after appending this coupon at the front
}
// 3) Reverse built order to play forward.
reverse(built.begin(), built.end());
// 4) Simulate forward; by construction this prefix is feasible from A.
auto [cnt, ans] = simulate_forward((ll)A, built);
// 5) OPTIONAL cheap tail: after the planned order, we may still afford extra T=1 with small P.
// Take remaining T=1 coupons in ascending P as much as possible; they cannot hurt feasibility already achieved.
// (We do a light pass without altering previously taken.)
{
// Gather remaining T=1 not used.
vector<pair<ll,int>> t1;
while (!pq[1].empty()) { t1.push_back(pq[1].top()); pq[1].pop(); }
sort(t1.begin(), t1.end()); // ascending P
// Re-simulate to the end of planned prefix to get current X, then append T=1 greedily.
ll X = A;
for (int i = 0; i < cnt; ++i) {
int id = ans[i];
ll p = P[id], t = T[id];
X = (X - p) * t; // feasible by construction
}
for (auto [p, id] : t1) {
if (X < p) break;
X -= p;
ans.push_back(id);
}
}
return ans;
}
