#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Standard types for calculation
typedef long long ll;
struct Coupon {
int id;
ll p;
ll t;
};
// Robust Comparator for Multipliers
// Uses __int128 to strictly ensure no overflow errors during sorting
bool compareMultipliers(const Coupon& a, const Coupon& b) {
// Priority: Free multipliers first
if (a.p == 0 && b.p > 0) return true;
if (b.p == 0 && a.p > 0) return false;
// Efficiency: Minimize P*T / (T-1)
unsigned __int128 val1 = (unsigned __int128)a.p * a.t * (b.t - 1);
unsigned __int128 val2 = (unsigned __int128)b.p * b.t * (a.t - 1);
if (val1 != val2) return val1 < val2;
return a.p < b.p;
}
bool compareSpenders(const Coupon& a, const Coupon& b) {
return a.p < b.p;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int n = P.size();
vector<Coupon> multipliers;
vector<Coupon> spenders;
ll total_spender_cost = 0;
ll total_multiplier_cost = 0;
// 1. Ingest and Separate
for (int i = 0; i < n; ++i) {
if (T[i] == 1) {
spenders.push_back({i, (ll)P[i], (ll)T[i]});
total_spender_cost += (ll)P[i];
} else {
multipliers.push_back({i, (ll)P[i], (ll)T[i]});
total_multiplier_cost += (ll)P[i];
}
}
// 2. Sort
sort(multipliers.begin(), multipliers.end(), compareMultipliers);
sort(spenders.begin(), spenders.end(), compareSpenders);
// 3. Precompute Spender Prefix Sums (for fast binary search)
int num_spenders = spenders.size();
vector<ll> spender_prefix(num_spenders + 1, 0);
for (int i = 0; i < num_spenders; ++i) {
spender_prefix[i+1] = spender_prefix[i] + spenders[i].p;
}
// 4. Setup DP
// We go up to 80 to be safe. 2^80 is effectively infinite.
int m = multipliers.size();
int limit_k = min(m, 80);
// dp[k] = max tokens having picked exactly k multipliers
vector<ll> dp(limit_k + 1, -1);
// reconstruction[k] stores the list of multiplier INDICES used to reach state dp[k]
// Since limit_k is small (80), storing a vector<int> for each state is fine (80 * 80 integers is tiny).
// This removes all ambiguity about "which previous state did I come from?".
vector<vector<int>> history(limit_k + 1);
// Initial State
dp[0] = A;
// Global Best Tracker
int max_coupons_count = -1;
vector<int> best_multiplier_indices; // Stores the indices of multipliers in the best solution
bool best_is_infinite = false; // Flag if the best solution involves buying "all remaining"
int best_split_index = -1; // If infinite, at which index in 'multipliers' did we switch strategy?
// Cap for "Infinite Money"
ll INF_CAP = total_spender_cost + total_multiplier_cost + 20000;
// Helper to update global best
auto update_best_standard = [&](int k, ll current_money, const vector<int>& used_muls) {
// How many spenders?
auto it = upper_bound(spender_prefix.begin(), spender_prefix.end(), current_money);
int cnt = (int)(it - spender_prefix.begin()) - 1;
if (k + cnt > max_coupons_count) {
max_coupons_count = k + cnt;
best_multiplier_indices = used_muls;
best_is_infinite = false;
}
};
// Check initial state (0 multipliers)
update_best_standard(0, A, {});
// Track cost of multipliers processed so far
ll current_mul_prefix_cost = 0;
// 5. Main Loop
for (int i = 0; i < m; ++i) {
ll cost = multipliers[i].p;
ll type = multipliers[i].t;
int id = multipliers[i].id;
// A. Check "Infinite Buy" Condition BEFORE processing this item
// Can we take a known state dp[k], and from there buy ALL remaining multipliers (i...m-1) and ALL spenders?
ll cost_remaining_muls = total_multiplier_cost - current_mul_prefix_cost;
ll cost_everything = cost_remaining_muls + total_spender_cost;
for (int k = 0; k <= limit_k; ++k) {
if (dp[k] != -1 && dp[k] >= cost_everything) {
int total = k + (m - i) + num_spenders;
if (total > max_coupons_count) {
max_coupons_count = total;
best_multiplier_indices = history[k];
best_is_infinite = true;
best_split_index = i;
}
}
}
// B. Update DP Table (Standard Knapsack Step)
// iterate backwards to avoid using same item twice for same depth
for (int k = limit_k - 1; k >= 0; --k) {
if (dp[k] != -1) {
if (dp[k] >= cost) {
ll next_tokens = dp[k] - cost;
// Safe Multiply
if (next_tokens > 0) {
if (INF_CAP / type < next_tokens) next_tokens = INF_CAP;
else next_tokens *= type;
}
// If this is a better way to reach k+1 coupons
if (next_tokens > dp[k+1]) {
dp[k+1] = next_tokens;
// Copy history from k and add current id
history[k+1] = history[k];
history[k+1].push_back(id);
}
}
}
}
current_mul_prefix_cost += cost;
// C. Check "Standard Best" Condition AFTER processing this item
// For every reachable state, see if we should stop taking multipliers and just buy spenders.
// (We only need to check the newly updated states, but checking all is safe and fast enough).
for (int k = 1; k <= limit_k; ++k) {
if (dp[k] != -1) {
update_best_standard(k, dp[k], history[k]);
}
}
}
// 6. Final "Infinite" check after all multipliers processed
// (Only relevant if we somehow have money left over after buying ALL multipliers sequentially)
// This is covered by `best_split_index` logic or `update_best_standard` at the very end.
// 7. Construct Final Result
vector<int> result;
if (best_is_infinite) {
// 1. Add the base multipliers from DP
result = best_multiplier_indices;
// 2. Add ALL remaining multipliers starting from split_index
for (int i = best_split_index; i < m; ++i) {
// Check if this ID is already in result?
// No, best_multiplier_indices only contains items from 0 to split_index-1.
// But we must be careful: 'history' stores IDs.
// The loop for Infinite Check ran at start of step i.
// So we take everything from index i onwards.
result.push_back(multipliers[i].id);
}
// 3. Add ALL spenders
for (const auto& s : spenders) {
result.push_back(s.id);
}
} else {
// Standard Solution
// 1. Add multipliers
result = best_multiplier_indices;
// 2. Add Spenders
// Re-calculate money to be absolutely precise
ll final_money = (ll)A;
// Use a map for O(1) property lookup during simulation
// Or just scan (since result size is small for multipliers part)
// Actually, we can just use the P/T values from original arrays if we trust IDs.
// Map ID -> index in original P/T arrays
// But we have P and T vectors passed in.
for (int id : result) {
ll p = P[id];
ll t = T[id];
if (final_money >= p) {
final_money = (final_money - p) * t;
if (final_money > INF_CAP) final_money = INF_CAP;
}
}
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.push_back(spenders[i].id);
}
}
return result;
}
