#include <bits/stdc++.h>
using namespace std;
struct ParentInfo {
int couponIdx; // original index of the coupon
int prev; // index in the parent vector of the previous state
ParentInfo(int c = -1, int p = -1) : couponIdx(c), prev(p) {}
};
/* --------------------------------------------------------------- */
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
const int N = (int)P.size();
/* -----------------------------------------------------------
split the coupons
----------------------------------------------------------- */
vector<int> multIdx; // indices with T > 1
vector<int> cheapIdx; // indices with T == 1
multIdx.reserve(N);
cheapIdx.reserve(N);
for (int i = 0; i < N; ++i) {
if (T[i] == 1) cheapIdx.push_back(i);
else multIdx.push_back(i);
}
/* -----------------------------------------------------------
sort multiplier coupons by w = Pi*Ti/(Ti-1)
(compare Pi*Ti*(Tj-1) < Pj*Tj*(Ti-1))
----------------------------------------------------------- */
sort(multIdx.begin(), multIdx.end(),
[&](int a, int b) {
long long left = 1LL * P[a] * T[a] * (T[b] - 1);
long long right = 1LL * P[b] * T[b] * (T[a] - 1);
if (left != right) return left < right;
return a < b; // deterministic tie‑break
});
/* -----------------------------------------------------------
DP over a constant number of taken multiplier coupons
----------------------------------------------------------- */
const int MAXK = 60; // > log2(1e9)
const long long INF = (1LL << 60);
vector<long long> dp(MAXK + 1, INF); // minimal loss D
vector<int> bestNode(MAXK + 1, -1); // index in parent list
dp[0] = 0; // no coupon, loss 0
int curMax = 0; // largest k with dp[k] < INF
vector<ParentInfo> parent; // pool of nodes
parent.reserve(multIdx.size() * 30);
for (int idx : multIdx) {
long long price = P[idx];
int Ti = T[idx];
long long Bi = 1LL * price * Ti - 1LL * A * (Ti - 1); // >0
for (int k = curMax; k >= 0; --k) {
if (dp[k] == INF) continue;
if (dp[k] <= (long long)A - price) { // affordable
long long newLoss = 1LL * Ti * dp[k] + Bi; // (4)
if (newLoss < dp[k + 1]) {
dp[k + 1] = newLoss;
parent.emplace_back(idx, bestNode[k]);
bestNode[k + 1] = (int)parent.size() - 1;
if (k + 1 > curMax) curMax = k + 1;
}
}
}
}
/* -----------------------------------------------------------
cheap coupons – sort by price and build prefix sums
----------------------------------------------------------- */
vector<pair<int,int>> cheap; // (price, original index)
cheap.reserve(cheapIdx.size());
for (int idx : cheapIdx) cheap.emplace_back(P[idx], idx);
sort(cheap.begin(), cheap.end(),
[&](const pair<int,int>& a, const pair<int,int>& b){
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
int C = (int)cheap.size();
vector<long long> pref(C + 1, 0);
for (int i = 1; i <= C; ++i) pref[i] = pref[i - 1] + cheap[i - 1].first;
/* -----------------------------------------------------------
choose the best number of multiplier coupons
----------------------------------------------------------- */
int bestK = 0, bestCheap = 0;
int bestTotal = -1;
for (int k = 0; k <= curMax; ++k) {
if (dp[k] == INF) continue;
long long tokensLeft = (long long)A - dp[k];
// maximal cheap coupons that fit into tokensLeft
int cheapCnt = (int)(upper_bound(pref.begin(), pref.end(), tokensLeft) - pref.begin() - 1);
int total = k + cheapCnt;
if (total > bestTotal) {
bestTotal = total;
bestK = k;
bestCheap = cheapCnt;
}
}
/* -----------------------------------------------------------
reconstruct the answer
----------------------------------------------------------- */
vector<int> answer;
// multiplier part (in the order we processed them)
vector<int> multSeq;
int node = bestNode[bestK];
while (node != -1) {
multSeq.push_back(parent[node].couponIdx);
node = parent[node].prev;
}
reverse(multSeq.begin(), multSeq.end());
answer.insert(answer.end(), multSeq.begin(), multSeq.end());
// cheap part: first bestCheap cheapest coupons
for (int i = 0; i < bestCheap; ++i) answer.push_back(cheap[i].second);
return answer;
}
