#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Struct to store coupon details
struct Coupon {
int id;
long long p;
long long t;
};
// Comparator for Multipliers (T > 1)
// We sort based on minimizing the "loss" ratio: P*T / (T-1).
// Logic: If we have coupon A and B, we prefer A before B if:
// P_a * T_a * (T_b - 1) < P_b * T_b * (T_a - 1)
bool compareMultipliers(const Coupon& a, const Coupon& b) {
// Use __int128 to prevent overflow during the cross-multiplication check
unsigned __int128 val1 = (unsigned __int128)a.p * a.t * (b.t - 1);
unsigned __int128 val2 = (unsigned __int128)b.p * b.t * (a.t - 1);
return val1 < val2;
}
// Comparator for Spenders (T = 1)
// Sort purely by cheapest price first.
bool compareSpenders(const Coupon& a, const Coupon& b) {
return a.p < b.p;
}
// RESTORED SIGNATURE TO MATCH GRADER: int A, vector<int> P, vector<int> T
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int n = P.size();
vector<Coupon> multipliers;
vector<Coupon> spenders;
// Cast inputs to long long internally
long long current_tokens = (long long)A;
// Calculate a cap for "infinite money"
long long INF = 0;
for (int price : P) INF += (long long)price;
INF += 1000;
// 1. Separate coupons
for (int i = 0; i < n; ++i) {
if (T[i] == 1) {
spenders.push_back({i, (long long)P[i], (long long)T[i]});
} else {
multipliers.push_back({i, (long long)P[i], (long long)T[i]});
}
}
// 2. Sort both lists
sort(multipliers.begin(), multipliers.end(), compareMultipliers);
sort(spenders.begin(), spenders.end(), compareSpenders);
// 3. DP on Multipliers
// We only check up to ~60 multipliers because 2^60 is > INF.
int m = multipliers.size();
int limit_k = min(m, 62);
// dp[k] = max tokens after buying exactly k multipliers
vector<long long> dp(limit_k + 1, -1);
// parent[k] stores which multiplier index (0 to m-1) was used to reach state k
// We need a 2D table to reconstruct correctly without ambiguity
// trace[k] = index of the multiplier in the `multipliers` vector that was added to reach state k
// However, since we iterate i from 0 to m, we need to store "at step i, did we update k?"
// Let's use `taken[i][k]` = boolean.
vector<vector<bool>> taken(m + 1, vector<bool>(limit_k + 1, false));
dp[0] = current_tokens;
for (int i = 0; i < m; ++i) {
long long cost = multipliers[i].p;
long long type = multipliers[i].t;
// Iterate backwards
for (int k = limit_k - 1; k >= 0; --k) {
if (dp[k] != -1) {
if (dp[k] >= cost) {
long long next_tokens = (dp[k] - cost) * type;
if (next_tokens > INF) next_tokens = INF;
if (next_tokens > dp[k+1]) {
dp[k+1] = next_tokens;
taken[i+1][k+1] = true;
}
}
}
}
}
// 4. Precompute Spender costs (Prefix Sums)
int s_size = spenders.size();
vector<long long> spender_prefix(s_size + 1, 0);
for (int i = 0; i < s_size; ++i) {
spender_prefix[i+1] = spender_prefix[i] + spenders[i].p;
}
// 5. Combine results
int max_count = 0;
int best_k = 0;
for (int k = 0; k <= limit_k; ++k) {
if (dp[k] == -1) continue;
long long money = dp[k];
// Binary search for spenders
auto it = upper_bound(spender_prefix.begin(), spender_prefix.end(), money);
int count_spenders = (int)(it - spender_prefix.begin()) - 1;
if (k + count_spenders > max_count) {
max_count = k + count_spenders;
best_k = k;
}
}
// 6. Reconstruct
vector<int> result_indices;
// A. Recover Multipliers
int cur_k = best_k;
// We must check if `taken[i][cur_k]` is true. If so, we came from `cur_k - 1`
// CAUTION: With 1D DP, simply checking taken[i][cur_k] is risky if we don't track
// exactly which 'previous' state we came from. But since we strictly iterate i=0..m
// and updated `taken` only on improvement, iterating backwards works.
// To be 100% safe against the "overwrite" problem in 1D DP reconstruction:
// We should pick the multipliers that actually contributed to the FINAL dp[best_k].
// Since we don't have the full 2D DP values, we rely on the fact that if taken[i][k] is true,
// it means multiplier `i-1` was the LAST one to update `dp[k]`.
// We iterate backwards from the last multiplier considered.
for (int i = m; i >= 1; --i) {
if (cur_k == 0) break;
if (taken[i][cur_k]) {
// Check if this transition is valid with current DP value?
// Actually, we can just trust the boolean if we assume the optimal path
// is composed of the "latest updates".
result_indices.push_back(multipliers[i-1].id);
cur_k--;
}
}
// Reverse to restore chronological order (Sorted Order)
reverse(result_indices.begin(), result_indices.end());
// B. Add Spenders
// Calculate exact money after buying the chosen multipliers
long long final_money = (long long)A;
// Verify calculation to be safe
for (int id : result_indices) {
// Find this coupon in multipliers list to get P and T
// (This is slow, O(N^2), but N is 60 here, so it's fine)
for (auto& m : multipliers) {
if (m.id == id) {
if (final_money >= m.p) {
final_money = (final_money - m.p) * m.t;
if (final_money > INF) final_money = INF;
}
break;
}
}
}
// Now pick spenders
auto it = upper_bound(spender_prefix.begin(), spender_prefix.end(), final_money);
int count_spenders = (int)(it - spender_prefix.begin()) - 1;
for (int i = 0; i < count_spenders; ++i) {
result_indices.push_back(spenders[i].id);
}
return result_indices;
}
