#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int price; // P[i]
int type; // T[i] (2,3,4)
int idx; // original index
long long C; // net loss at start, formula (5)
};
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
const int N = (int)P.size();
/* -------------------------------------------------------------
split coupons into high (T>1) and cheap (T==1), discard
those with price > A (they can never be bought)
------------------------------------------------------------- */
vector<Coupon> high;
struct Cheap { int price; int idx; };
vector<Cheap> cheap;
for (int i = 0; i < N; ++i) {
if (P[i] > A) continue; // never affordable
if (T[i] == 1) {
cheap.push_back({P[i], i});
} else {
long long C = 1LL * T[i] * P[i] - 1LL * (T[i] - 1) * A;
high.push_back({P[i], T[i], i, C});
}
}
/* --------------- cheap coupons : sort by price -------------- */
sort(cheap.begin(), cheap.end(),
[](const Cheap& a, const Cheap& b) {
if (a.price != b.price) return a.price < b.price;
return a.idx < b.idx;
});
vector<long long> cheapPref(cheap.size() + 1, 0);
for (size_t i = 0; i < cheap.size(); ++i)
cheapPref[i + 1] = cheapPref[i] + cheap[i].price;
/* --------------- high coupons : sort by V ------------------- */
sort(high.begin(), high.end(),
[&](const Coupon& a, const Coupon& b) {
long long left = 1LL * a.price * a.type * (b.type - 1);
long long right = 1LL * b.price * b.type * (a.type - 1);
if (left != right) return left < right; // smaller V first
if (a.C != b.C) return a.C < b.C; // tie‑break by net loss
return a.idx < b.idx;
});
const int M = (int)high.size();
const int K = min(M, 60); // safe upper bound (≈30)
/* -------------------------------------------------------------
DP: dp[i][c] – maximal remaining tokens after considering
first i high coupons and buying exactly c of them
we keep only two rows for the values, but we store the
whole decision table "taken" for back‑tracking
------------------------------------------------------------- */
const long long NEG = -1;
vector<long long> dpPrev(K + 1, NEG), dpCurr(K + 1, NEG);
dpPrev[0] = A;
// decision table: taken[i][c] == 1 iff coupon i (1‑based) is taken to obtain dp[i][c]
vector<char> taken((M + 1) * (K + 1), 0);
for (int i = 1; i <= M; ++i) {
const Coupon& cp = high[i - 1];
// copy the “skip” case
for (int c = 0; c <= K; ++c) dpCurr[c] = dpPrev[c];
// try to take the i‑th coupon
for (int c = 1; c <= K; ++c) {
if (dpPrev[c - 1] != NEG && dpPrev[c - 1] >= cp.price) {
long long newX = (dpPrev[c - 1] - cp.price) * 1LL * cp.type;
if (newX > dpCurr[c]) {
dpCurr[c] = newX;
taken[i * (K + 1) + c] = 1;
}
}
}
dpPrev.swap(dpCurr);
}
/* -------------------------------------------------------------
choose the best number of high coupons (c) together with cheap ones
------------------------------------------------------------- */
long long bestTotal = 0;
int bestC = 0;
long long bestTokens = A; // tokens after the chosen high coupons
for (int c = 0; c <= K; ++c) {
long long tokens = dpPrev[c];
if (tokens == NEG) continue;
// maximal number of cheap coupons we can still afford
int cheapCnt = (int)(upper_bound(cheapPref.begin(),
cheapPref.end(),
tokens) - cheapPref.begin()) - 1;
long long total = (long long)c + cheapCnt;
if (total > bestTotal) {
bestTotal = total;
bestC = c;
bestTokens = tokens;
}
}
/* -------------------------------------------------------------
reconstruct the chosen high coupons
------------------------------------------------------------- */
vector<int> chosenHigh;
int c = bestC;
for (int i = M; i >= 1 && c > 0; --i) {
if (taken[i * (K + 1) + c]) {
chosenHigh.push_back(high[i - 1].idx);
--c;
}
}
reverse(chosenHigh.begin(), chosenHigh.end());
/* -------------------------------------------------------------
add cheap coupons (the cheapest ones that still fit)
------------------------------------------------------------- */
int cheapCnt = (int)(upper_bound(cheapPref.begin(),
cheapPref.end(),
bestTokens) - cheapPref.begin()) - 1;
vector<int> answer;
answer.reserve(chosenHigh.size() + cheapCnt);
answer.insert(answer.end(), chosenHigh.begin(), chosenHigh.end());
for (int i = 0; i < cheapCnt; ++i)
answer.push_back(cheap[i].idx);
return answer;
}
