#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx; // original index
long long P; // price
int T; // type (multiplier)
long long num; // T * P
int den; // T - 1 (0 for T == 1, meaning infinite key)
};
static const __int128 INF = (__int128)4'000'000'000'000'000'000LL; // sufficiently large
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
vector<Coupon> cur(N);
for (int i = 0; i < N; ++i) {
cur[i].idx = i;
cur[i].P = P[i];
cur[i].T = T[i];
cur[i].num = (long long)T[i] * (long long)P[i];
cur[i].den = T[i] - 1; // 0 for T==1
}
// sort by increasing v = T*P/(T-1); treat T==1 as +infinity
sort(cur.begin(), cur.end(), [](const Coupon& a, const Coupon& b) {
if (a.den == 0 && b.den == 0) {
// both type 1, order by price (cheapest first, any tie is fine)
return a.P < b.P;
}
if (a.den == 0) return false; // a is type 1 -> larger key
if (b.den == 0) return true; // b is type 1 -> larger key
__int128 lhs = (__int128)a.num * b.den;
__int128 rhs = (__int128)b.num * a.den;
if (lhs != rhs) return lhs < rhs;
// tie‑break by price
return a.P < b.P;
});
// DP: dp[i][k] = maximal tokens after considering first i coupons and buying exactly k of them
vector<vector<__int128>> dp(N + 1, vector<__int128>(N + 1, -1));
vector<vector<char>> take(N + 1, vector<char>(N + 1, -1)); // 1 = taken, 0 = skipped
dp[0][0] = A;
for (int i = 0; i < N; ++i) {
const Coupon& c = cur[i];
for (int k = 0; k <= i; ++k) {
if (dp[i][k] < 0) continue;
// Skip this coupon
if (dp[i][k] > dp[i + 1][k]) {
dp[i + 1][k] = dp[i][k];
take[i + 1][k] = 0;
}
// Take this coupon if affordable
if (dp[i][k] >= (__int128)c.P) {
__int128 newToken = (dp[i][k] - (__int128)c.P) * (__int128)c.T;
if (newToken > INF) newToken = INF;
if (newToken > dp[i + 1][k + 1]) {
dp[i + 1][k + 1] = newToken;
take[i + 1][k + 1] = 1;
}
}
}
}
// Find the maximum number of coupons we can buy
int bestK = 0;
for (int k = 0; k <= N; ++k) {
if (dp[N][k] >= 0) bestK = k;
}
// Reconstruct the sequence
vector<int> revResult;
int i = N, k = bestK;
while (i > 0) {
if (take[i][k] == 1) {
revResult.push_back(cur[i - 1].idx);
--k;
}
// if take[i][k] == 0 we simply skip this coupon
--i;
}
reverse(revResult.begin(), revResult.end());
return revResult;
}
