#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx; // original index
long long P; // price
int T; // multiplier
};
static long long ceilDiv(long long a, int b) {
// a >= 0 , b >= 1
return (a + b - 1) / b;
}
// ---------------------------------------------------------------
// max_coupons : required function
// ---------------------------------------------------------------
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
vector<Coupon> all(N);
for (int i = 0; i < N; ++i) {
all[i] = {i, (long long)P[i], T[i]};
}
/* ---------- sort by increasing R = P*T/(T-1) ----------
T = 1 → R = +∞ (they are placed after all T>1) */
auto cmp = [](const Coupon& a, const Coupon& b) -> bool {
bool a_one = (a.T == 1);
bool b_one = (b.T == 1);
if (a_one && b_one) return a.idx < b.idx; // any stable order
if (a_one) return false; // a after b
if (b_one) return true; // a before b
__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;
if (a.P != b.P) return a.P < b.P; // tie‑break
return a.idx < b.idx;
};
sort(all.begin(), all.end(), cmp);
/* ---------- DP over the list, processed from large R to small R ----------
reverse order → we always add the current coupon at the front */
vector<Coupon> order = all;
reverse(order.begin(), order.end());
const long long INF = (1LL << 60);
vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF));
vector<vector<char>> take(N + 1, vector<char>(N + 1, 0));
dp[0][0] = 0; // empty set
for (int i = 0; i < N; ++i) {
// initialise row i+1
for (int k = 0; k <= i + 1; ++k) {
dp[i + 1][k] = INF;
take[i + 1][k] = 0;
}
// skip the i‑th coupon
for (int k = 0; k <= i; ++k) {
if (dp[i][k] < dp[i + 1][k]) {
dp[i + 1][k] = dp[i][k];
take[i + 1][k] = 0;
}
}
// take the i‑th coupon (it becomes the first one)
const Coupon& c = order[i];
for (int k = 0; k <= i; ++k) {
if (dp[i][k] == INF) continue;
long long cand = c.P + ceilDiv(dp[i][k], c.T);
if (cand < dp[i + 1][k + 1]) {
dp[i + 1][k + 1] = cand;
take[i + 1][k + 1] = 1;
}
}
}
// largest feasible number of coupons
int bestK = 0;
for (int k = N; k >= 0; --k) {
if (dp[N][k] <= (long long)A) {
bestK = k;
break;
}
}
// reconstruct the purchase order (forward order)
vector<int> answer;
int i = N, k = bestK;
while (i > 0) {
if (k > 0 && take[i][k]) {
answer.push_back(order[i - 1].idx); // original index
--k;
--i;
} else {
--i; // coupon was skipped
}
}
// the `answer` vector already contains the coupons in the order they
// have to be bought.
return answer;
}
