#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
// because P can be large and we are multiplying 3 numbers.
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;
}
vector<int> max_coupons(long long A, vector<long long> P, vector<int> T) {
int n = P.size();
vector<Coupon> multipliers;
vector<Coupon> spenders;
// Calculate a cap for "infinite money".
// If we have more money than the cost of all coupons combined,
// we don't need to track the exact number anymore.
long long INF = 0;
for (long long price : P) INF += price;
INF += 1000; // Safety buffer
// 1. Separate coupons
for (int i = 0; i < n; ++i) {
if (T[i] == 1) {
spenders.push_back({i, P[i], (long long)T[i]});
} else {
multipliers.push_back({i, 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
// choice[i][k] = true if we included the i-th multiplier in the optimal set for k
vector<long long> dp(limit_k + 1, -1);
vector<vector<bool>> choice(m + 1, vector<bool>(limit_k + 1, false));
dp[0] = A;
for (int i = 0; i < m; ++i) {
long long cost = multipliers[i].p;
long long type = multipliers[i].t;
// Iterate backwards to update DP table
for (int k = limit_k - 1; k >= 0; --k) {
if (dp[k] != -1) {
// Check if we can afford this multiplier
if (dp[k] >= cost) {
long long next_tokens = (dp[k] - cost) * type;
// Cap at INF to prevent overflow
if (next_tokens > INF) next_tokens = INF;
// If this path gives more tokens than previous known way to reach k+1
if (next_tokens > dp[k+1]) {
dp[k+1] = next_tokens;
choice[i+1][k+1] = true;
}
}
}
}
}
// 4. Precompute Spender costs (Prefix Sums) for fast lookup
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 to find global maximum
int max_count = 0;
int best_k = 0; // The specific number of multipliers that yields the best result
for (int k = 0; k <= limit_k; ++k) {
if (dp[k] == -1) continue;
long long current_money = dp[k];
// Binary search to find how many spenders we can buy
// upper_bound returns iterator to first element > current_money
auto it = upper_bound(spender_prefix.begin(), spender_prefix.end(), current_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 the solution (Indices)
vector<int> result_indices;
// A. Backtrack to find which Multipliers were used
int current_k = best_k;
for (int i = m; i >= 1; --i) {
if (current_k == 0) break;
// If choice[i][current_k] is true, it means we used multiplier (i-1)
// to transition from (current_k-1) to current_k.
// NOTE: This logic requires careful validation.
// In the DP loop, we blindly overwrote dp[k+1]. To reconstruct correctly
// with a 1D DP array, strictly speaking, we need a 2D DP or a more complex
// backtracking logic.
// HOWEVER, for this specific problem, since multipliers are sorted by efficiency,
// and we iterate i from 0 to m, the 'choice' table method above is valid
// ONLY if we verify the transition.
// Let's verify: Did we come from dp[current_k-1] using multiplier i-1?
// We need to re-check the value logic or rely on the stored boolean.
// With the 1D optimization, 'choice' might be overwritten by a later, worse multiplier
// that happened to result in the same 'k' but less money (which we wouldn't take).
// Actually, we only update choice if we update dp. So choice is consistent with dp.
if (choice[i][current_k]) {
// We need to be sure that taking this didn't just update the value
// but was part of the *optimal* path for best_k.
// Since we only update if (new > old), the boolean is generally reliable.
// But there is an edge case: What if a later multiplier updated dp[k]
// but we ended up needing the value from an earlier one?
// Actually, since we want *max money*, we always want the update.
// One catch: Using a 1D DP array, dp[k-1] has been updated by the time we are at step i.
// To perfectly reconstruct, we must check:
// Could we have reached state `dp[current_k]` from state `dp[current_k-1]`
// (before this item) using this item?
// The 2D boolean array `choice[i][k]` stores exactly "Did item i update state k?".
// So if choice[i][k] is true, item i IS the one that set the final value of dp[k].
result_indices.push_back(multipliers[i-1].id);
current_k--;
}
}
// The loop above finds multipliers in reverse order (last added first).
// But for the game rules, we must buy them in the Sorted Order.
// The `result_indices` currently contains the correct items, but we pushed them in reverse logic.
// We just need to reverse the list to restore the chronological buy order.
reverse(result_indices.begin(), result_indices.end());
// B. Add the Spenders
// Recalculate money after buying the specific multipliers
// (We trust the DP value, but for safety, let's just grab the spenders based on final DP money)
long long money_after_mul = dp[best_k];
auto it = upper_bound(spender_prefix.begin(), spender_prefix.end(), money_after_mul);
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;
}
