#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
struct Mult {
int idx;
int64 P;
int T;
};
static bool cmpMult(const Mult& a, const Mult& b) {
// Compare a.P * a.T / (a.T-1) < b.P * b.T / (b.T-1)
// cross‑multiply: a.P * a.T * (b.T-1) < b.P * b.T * (a.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;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
vector<Mult> mult;
vector<int> oneIdx; // indices with T == 1
for (int i = 0; i < N; ++i) {
if (T[i] == 1) oneIdx.push_back(i);
else mult.push_back({i, (int64)P[i], T[i]});
}
// sort multipliers by the metric Pi*Ti/(Ti-1)
sort(mult.begin(), mult.end(), cmpMult);
int M = (int)mult.size();
const i128 INF = (i128)4'000'000'000'000'000'000LL; // 4·10^18, far larger than any needed value
// dp[i][k] = maximal token after considering first i multipliers and taking exactly k of them
vector<vector<i128>> dp(M + 1, vector<i128>(M + 1, -1));
vector<vector<char>> take(M + 1, vector<char>(M + 1, 0));
dp[0][0] = (i128)A;
for (int i = 1; i <= M; ++i) {
const Mult& cur = mult[i - 1];
// not taking this coupon
for (int k = 0; k <= i; ++k) {
dp[i][k] = dp[i - 1][k];
take[i][k] = 0;
}
// trying to take it
for (int k = 1; k <= i; ++k) {
if (dp[i - 1][k - 1] != -1 && dp[i - 1][k - 1] >= (i128)cur.P) {
i128 newToken = (dp[i - 1][k - 1] - (i128)cur.P) * (i128)cur.T;
if (newToken > INF) newToken = INF;
if (newToken > dp[i][k]) {
dp[i][k] = newToken;
take[i][k] = 1;
} else if (newToken == dp[i][k] && !take[i][k]) {
// Prefer a path that takes the coupon (helps reconstruction)
take[i][k] = 1;
}
}
}
}
// sort type‑1 coupons by price (to maximise count later)
sort(oneIdx.begin(), oneIdx.end(),
[&](int a, int b) { return P[a] < P[b]; });
int bestTotal = -1;
int bestK = 0;
i128 bestToken = -1;
// evaluate each possible number of taken multipliers
for (int k = 0; k <= M; ++k) {
if (dp[M][k] == -1) continue;
i128 token = dp[M][k];
i128 cur = token;
int tCnt = 0;
for (int idx : oneIdx) {
if (cur >= (i128)P[idx]) {
cur -= (i128)P[idx];
++tCnt;
} else break;
}
int total = k + tCnt;
if (total > bestTotal) {
bestTotal = total;
bestK = k;
bestToken = token;
}
}
// reconstruct the chosen multipliers
vector<int> answer;
int curK = bestK;
for (int i = M; i >= 1; --i) {
if (curK > 0 && take[i][curK]) {
answer.push_back(mult[i - 1].idx);
--curK;
}
}
reverse(answer.begin(), answer.end());
// apply the remaining token to take type‑1 coupons greedily
i128 token = bestToken;
for (int idx : oneIdx) {
if (token >= (i128)P[idx]) {
token -= (i128)P[idx];
answer.push_back(idx);
} else break;
}
return answer;
}
