#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
const int64 INF = (1LL << 60); // big enough, far larger than any price sum
// multiply and subtract with saturation at INF
static inline int64 apply(int64 cur, int64 price, int mult) {
if (cur == INF) return INF;
if (cur < price) return -1; // cannot buy
i128 val = (i128)(cur - price) * mult;
if (val > INF) return INF;
return (int64)val;
}
// --------------------------------------------------------------------
struct MulCoupon {
int idx; // original index
int64 P;
int T;
};
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
/* -------- separate the two groups -------- */
vector<MulCoupon> mul; // T > 1
vector<pair<int64,int>> cheap; // price , index (T == 1)
for (int i = 0; i < N; ++i) {
if (T[i] == 1) cheap.emplace_back((int64)P[i], i);
else mul.push_back({i, (int64)P[i], T[i]});
}
/* -------- sort multipliers by K = P*T/(T-1) -------- */
auto cmpK = [](const MulCoupon& a, const MulCoupon& b) {
// compare a.P * a.T / (a.T-1) < b.P * b.T / (b.T-1)
i128 left = (i128)a.P * a.T * (b.T - 1);
i128 right = (i128)b.P * b.T * (a.T - 1);
return left < right;
};
sort(mul.begin(), mul.end(), cmpK);
int M = (int)mul.size();
/* -------- DP over the sorted multipliers -------- */
vector<vector<int64>> best(M + 1, vector<int64>(M + 1, -1));
// predecessor: {previous k , taken?}
vector<vector<pair<int,bool>>> pre(M + 1, vector<pair<int,bool>>(M + 1, {-1,false}));
best[0][0] = (int64)A;
for (int i = 0; i < M; ++i) {
for (int k = 0; k <= i; ++k) {
if (best[i][k] == -1) continue;
// not take coupon i
if (best[i][k] > best[i + 1][k]) {
best[i + 1][k] = best[i][k];
pre[i + 1][k] = {k, false};
}
// take coupon i, if affordable
if (best[i][k] >= mul[i].P) {
int64 nxt = apply(best[i][k], mul[i].P, mul[i].T);
if (nxt > best[i + 1][k + 1]) {
best[i + 1][k + 1] = nxt;
pre[i + 1][k + 1] = {k, true};
}
}
}
}
/* -------- cheap coupons: sort by price and prefix sums -------- */
sort(cheap.begin(), cheap.end(),
[](const pair<int64,int>& a, const pair<int64,int>& b){
return a.first < b.first;
});
int C = (int)cheap.size();
vector<int64> 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 multipliers -------- */
int bestTotal = 0;
int bestK = 0; // how many multipliers are used
int bestCheap = 0; // how many cheap coupons are taken
for (int k = 0; k <= M; ++k) {
int64 tok = best[M][k];
if (tok < 0) continue; // unreachable
// maximal cheap coupons we can afford
int cheapCnt = 0;
if (tok >= pref[C]) cheapCnt = C;
else {
// binary search on prefix sums
int lo = 0, hi = C;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (pref[mid] <= tok) lo = mid;
else hi = mid - 1;
}
cheapCnt = lo;
}
int total = k + cheapCnt;
if (total > bestTotal) {
bestTotal = total;
bestK = k;
bestCheap = cheapCnt;
}
}
/* -------- reconstruct the chosen multipliers -------- */
vector<int> answer;
int i = M;
int k = bestK;
while (i > 0) {
auto pr = pre[i][k];
int prevK = pr.first;
bool took = pr.second;
if (took) {
answer.push_back(mul[i - 1].idx); // coupon i-1 was taken
}
k = prevK;
--i;
}
reverse(answer.begin(), answer.end()); // correct chronological order
/* -------- add the cheap coupons -------- */
for (int idx = 0; idx < bestCheap; ++idx)
answer.push_back(cheap[idx].second);
return answer; // possibly empty
}
