#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 60); // large enough, behaves as "infinite"
struct Coupon {
int idx; // original index
long long price;
int t; // multiplier (2,3,4)
};
/* comparison by need = price * t / (t-1) (ascending) */
static bool needCmp(const Coupon& a, const Coupon& b) {
// compare a.price * a.t * (b.t-1) < b.price * b.t * (a.t-1)
__int128 lhs = (__int128)a.price * a.t * (b.t - 1);
__int128 rhs = (__int128)b.price * b.t * (a.t - 1);
return lhs < rhs;
}
/* multiply with saturation at INF */
static long long mul_sat(long long x, int mul) {
if (x >= INF) return INF;
__int128 prod = (__int128)x * mul;
if (prod > INF) return INF;
return (long long)prod;
}
/* --------------------------------------------------------------- */
vector<int> max_coupons(int A_int, vector<int> P, vector<int> T) {
long long A = A_int;
int N = (int)P.size();
/* split coupons ----------------------------------------------------- */
vector<Coupon> mult; // T > 1
vector<pair<long long,int>> cheap; // T == 1 (price , original idx)
for (int i = 0; i < N; ++i) {
if (T[i] == 1) {
cheap.emplace_back(P[i], i);
} else {
mult.push_back({i, P[i], T[i]});
}
}
/* sort cheap by price, mult by need (see Lemma 1) -------------------- */
sort(cheap.begin(), cheap.end(),
[](const auto& a, const auto& b){ return a.first < b.first; });
sort(mult.begin(), mult.end(), needCmp);
int M = (int)mult.size();
/* DP tables ---------------------------------------------------------- */
// dp[i][k] – after first i coupons, taking exactly k of them,
// maximum token amount ( -1 = unreachable )
vector<vector<long long>> dp(M+1, vector<long long>(M+1, -1));
vector<vector<char>> take(M+1, vector<char>(M+1, 0)); // did we take i‑th coupon?
dp[0][0] = A;
for (int i = 1; i <= M; ++i) {
const Coupon &c = mult[i-1];
for (int k = 0; k <= i; ++k) {
// case: do not take this coupon
dp[i][k] = dp[i-1][k];
take[i][k] = 0;
// case: take it (need k>=1)
if (k > 0 && dp[i-1][k-1] >= c.price) {
long long before = dp[i-1][k-1] - c.price;
long long after = mul_sat(before, c.t);
if (after > dp[i][k]) {
dp[i][k] = after;
take[i][k] = 1;
}
}
}
}
/* prefix sums of cheap coupons --------------------------------------- */
int Ccheap = (int)cheap.size();
vector<long long> pref(Ccheap+1, 0);
for (int i = 1; i <= Ccheap; ++i) pref[i] = pref[i-1] + cheap[i-1].first;
/* find best total ---------------------------------------------------- */
int bestK = 0;
int bestCheap = 0;
long long bestToken = -1;
int bestTotal = -1;
for (int k = 0; k <= M; ++k) {
long long tok = dp[M][k];
if (tok < 0) continue;
int cheapCnt;
if (tok >= INF) {
cheapCnt = Ccheap;
} else {
// largest w with pref[w] <= tok
cheapCnt = (int)(upper_bound(pref.begin(), pref.end(), tok) - pref.begin() - 1);
}
int total = k + cheapCnt;
if (total > bestTotal) {
bestTotal = total;
bestK = k;
bestCheap = cheapCnt;
bestToken = tok;
}
}
if (bestTotal <= 0) return {}; // nothing can be bought
/* reconstruct the chosen mult coupons -------------------------------- */
vector<int> seqMult;
int i = M, k = bestK;
while (i > 0) {
if (take[i][k]) {
seqMult.push_back(mult[i-1].idx);
--k;
}
--i;
}
reverse(seqMult.begin(), seqMult.end());
/* add the cheap coupons */
vector<int> result = seqMult;
for (int i = 0; i < bestCheap; ++i) result.push_back(cheap[i].second);
return result;
}
