#include <vector>
#include <algorithm>
using namespace std;
struct Coupon {
long long P, T;
int id;
};
// Sort T > 1 coupons by P_i * T_i / (T_i - 1) ascending
bool comp_Tgt1(const Coupon& a, const Coupon& b) {
long long lhs = a.P * a.T * (b.T - 1);
long long rhs = b.P * b.T * (a.T - 1);
if (lhs != rhs) return lhs < rhs;
return a.id < b.id;
}
// Sort T == 1 coupons by P_i ascending
bool comp_Teq1(const Coupon& a, const Coupon& b) {
if (a.P != b.P) return a.P < b.P;
return a.id < b.id;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int n = P.size();
vector<Coupon> t_gt_1;
vector<Coupon> t_eq_1;
for (int i = 0; i < n; ++i) {
if (T[i] > 1) {
t_gt_1.push_back({(long long)P[i], (long long)T[i], i});
} else {
t_eq_1.push_back({(long long)P[i], (long long)T[i], i});
}
}
sort(t_gt_1.begin(), t_gt_1.end(), comp_Tgt1);
sort(t_eq_1.begin(), t_eq_1.end(), comp_Teq1);
long long X = A;
vector<int> ans;
// Cap X to prevent overflow but ensure we stay wealthy enough to afford any coupon
long long INF = 2000000000000000LL;
vector<Coupon> loss_list;
bool loss_started = false;
// Process Gain/Neutral T > 1 coupons
for (const auto& c : t_gt_1) {
if (!loss_started) {
long long lhs = X * (c.T - 1);
long long rhs = c.P * c.T;
if (lhs >= rhs) { // Gain or Neutral phase
X = (X - c.P) * c.T;
X = min(X, INF);
ans.push_back(c.id);
} else {
loss_started = true;
loss_list.push_back(c);
}
} else {
loss_list.push_back(c);
}
}
int M = loss_list.size();
int K_MAX = 65; // Safe upper bound for consecutive valid Loss purchases
// 1D DP table for 0/1 Knapsack optimization
vector<long long> dp(K_MAX + 1, -1);
vector<vector<bool>> parent(M + 1, vector<bool>(K_MAX + 1, false));
dp[0] = X;
for (int i = 1; i <= M; ++i) {
long long p_val = loss_list[i-1].P;
long long t_val = loss_list[i-1].T;
// Iterate backwards for optimized 1D state transition
for (int k = K_MAX; k >= 1; --k) {
if (dp[k-1] != -1 && dp[k-1] >= p_val) {
long long val = (dp[k-1] - p_val) * t_val;
val = min(val, INF);
if (val > dp[k]) {
dp[k] = val;
parent[i][k] = true;
}
}
}
}
vector<long long> pref(t_eq_1.size() + 1, 0);
for (size_t i = 0; i < t_eq_1.size(); ++i) {
pref[i+1] = pref[i] + t_eq_1[i].P;
}
int best_k = -1;
int max_total = -1;
int best_c = -1;
// Check optimal combination of Loss coupons + T=1 additive coupons
for (int k = 0; k <= K_MAX; ++k) {
if (dp[k] != -1) {
long long rem = dp[k];
int c = upper_bound(pref.begin(), pref.end(), rem) - pref.begin() - 1;
if (k + c > max_total) {
max_total = k + c;
best_k = k;
best_c = c;
}
}
}
// Reconstruct the picked path among "Loss" multiplier coupons
if (best_k > 0) {
int curr_k = best_k;
vector<int> loss_picks;
for (int i = M; i >= 1; --i) {
if (curr_k > 0 && parent[i][curr_k]) {
loss_picks.push_back(loss_list[i-1].id);
curr_k--;
}
}
reverse(loss_picks.begin(), loss_picks.end());
for (int id : loss_picks) {
ans.push_back(id);
}
}
// Spend the remaining tokens strictly on optimal T = 1 coupons
for (int i = 0; i < best_c; ++i) {
ans.push_back(t_eq_1[i].id);
}
return ans;
}
