#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx;
long long P;
int T;
};
struct Node {
__int128 token; // tokens after processing this state
int cnt; // number of multipliers taken
int prev; // previous node id
int couponIdx; // original index of the coupon taken to reach here (-1 for start)
};
static const __int128 INF = (__int128)4'000'000'000'000'000'000LL; // sufficiently large
// comparator based on K = P*T/(T-1)
bool cmpCoupon(const Coupon& a, const Coupon& b) {
if (a.T == 1 && b.T == 1) return a.idx < b.idx;
if (a.T == 1) return false; // a after b
if (b.T == 1) return true; // a before b
// both T > 1
__int128 left = (__int128)a.P * a.T * (b.T - 1);
__int128 right = (__int128)b.P * b.T * (a.T - 1);
if (left != right) return left < right;
return a.idx < b.idx;
}
// count of cheap coupons (T==1) we can afford with token X
int cheapCount(__int128 X,
const vector<unsigned long long>& pref,
unsigned long long totalCheapSum) {
if (X <= 0) return 0;
if (X >= ( __int128)totalCheapSum) return (int)pref.size() - 1;
unsigned long long x = (unsigned long long)X;
// pref[0]=0, pref[i] = sum of first i cheap coupons (i from 0..M)
int pos = upper_bound(pref.begin(), pref.end(), x) - pref.begin() - 1;
return pos;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int N = (int)P.size();
vector<Coupon> all;
all.reserve(N);
for (int i = 0; i < N; ++i) {
all.push_back({i, (long long)P[i], T[i]});
}
sort(all.begin(), all.end(), cmpCoupon);
// split into multipliers (T>1) and cheap (T==1)
vector<Coupon> mult; // T>1
vector<Coupon> cheap; // T==1
for (auto &c : all) {
if (c.T == 1) cheap.push_back(c);
else mult.push_back(c);
}
// cheap coupons: sort by price asc for later selection
sort(cheap.begin(), cheap.end(),
[](const Coupon& a, const Coupon& b){ return a.P < b.P; });
vector<unsigned long long> cheapPref;
cheapPref.push_back(0);
for (auto &c : cheap) {
cheapPref.push_back(cheapPref.back() + (unsigned long long)c.P);
}
unsigned long long totalCheapSum = cheapPref.back();
// DP over multipliers
vector<Node> nodes;
nodes.reserve(500000);
// start node
nodes.push_back({ (__int128)A, 0, -1, -1 });
vector<int> cur; // ids of nondominated states
cur.push_back(0);
// best answer variables
long long bestTotal = cheapCount((__int128)A, cheapPref, totalCheapSum);
int bestNodeId = -1; // -1 denotes using no multipliers
__int128 bestToken = (__int128)A;
for (size_t i = 0; i < mult.size(); ++i) {
const Coupon& curC = mult[i];
// map: cnt -> node id with maximal token for that cnt
unordered_map<int,int> best;
best.reserve(cur.size()*2 + 4);
for (int nid : cur) {
const Node& nd = nodes[nid];
// skip this coupon
auto it = best.find(nd.cnt);
if (it == best.end() || nodes[it->second].token < nd.token)
best[nd.cnt] = nid;
// take this coupon if possible
if (nd.token >= (__int128)curC.P) {
__int128 newTok = (nd.token - (__int128)curC.P) * (__int128)curC.T;
if (newTok > INF) newTok = INF;
int newCnt = nd.cnt + 1;
Node newNode{newTok, newCnt, nid, curC.idx};
int newId = (int)nodes.size();
nodes.push_back(newNode);
auto it2 = best.find(newCnt);
if (it2 == best.end() || nodes[it2->second].token < newTok)
best[newCnt] = newId;
}
}
// collect and prune dominated states
vector<pair<int,int>> vec;
vec.reserve(best.size());
for (auto &kv : best) vec.emplace_back(kv.first, kv.second);
sort(vec.begin(), vec.end(),
[](const pair<int,int>& a, const pair<int,int>& b){ return a.first < b.first; });
cur.clear();
__int128 bestTokenSeen = -1;
for (int idx = (int)vec.size() - 1; idx >= 0; --idx) {
int nid = vec[idx].second;
__int128 tok = nodes[nid].token;
if (tok > bestTokenSeen) {
cur.push_back(nid);
bestTokenSeen = tok;
}
}
// update answer using current states
for (int nid : cur) {
const Node& nd = nodes[nid];
int cheapCan = cheapCount(nd.token, cheapPref, totalCheapSum);
long long total = (long long)nd.cnt + cheapCan;
if (total > bestTotal) {
bestTotal = total;
bestNodeId = nid;
bestToken = nd.token;
}
}
}
// also consider the case of using no multipliers (already handled)
// reconstruct answer
vector<int> answer;
if (bestNodeId != -1) {
// backtrack multiplier indices
int curId = bestNodeId;
while (curId != -1 && nodes[curId].couponIdx != -1) {
answer.push_back(nodes[curId].couponIdx);
curId = nodes[curId].prev;
}
reverse(answer.begin(), answer.end());
// token after taking those multipliers
} else {
// no multipliers taken
bestToken = (__int128)A;
}
// add cheap coupons (as many as possible)
int cheapCan = cheapCount(bestToken, cheapPref, totalCheapSum);
for (int i = 0; i < cheapCan; ++i) {
answer.push_back(cheap[i].idx);
}
return answer;
}
