#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
// Define long long for calculations to prevent overflow
typedef long long ll;
const ll MAX_VAL = 2e15; // Cap to prevent overflow, exceeding sum of prices
// Helper to sort reconstruction
struct Step {
int type_idx; // 0 for type 2, 1 for type 3, 2 for type 4
int index_in_vector; // Index in the specific type vector
};
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int n = P.size();
// 1. Separate coupons by Type
// v[0] = Type 1 (Spenders), v[1] = Type 2, v[2] = Type 3, v[3] = Type 4
// Store pairs of {Price, Original_Index}
vector<vector<pair<ll, int>>> v(4);
for (int i = 0; i < n; ++i) {
v[T[i] - 1].push_back({(ll)P[i], i});
}
// 2. Sort each type by Price (Cheapest first)
for (int i = 0; i < 4; ++i) {
sort(v[i].begin(), v[i].end());
}
// 3. Pre-calculate "Profit" phase (Greedy Heuristic)
// We combine all Multipliers (Type 2,3,4) into a list to check for "money makers"
struct MetaCoupon {
int type_minus_1; // 1, 2, 3 corresponding to Types 2, 3, 4
int vec_idx;
ll p;
};
vector<MetaCoupon> candidates;
for (int t = 1; t < 4; ++t) {
for (int i = 0; i < v[t].size(); ++i) {
candidates.push_back({t, i, v[t][i].first});
}
}
// Sort by the efficiency ratio: P*T / (T-1)
// We use the cross-multiplication comparison from the user's code/previous logic
sort(candidates.begin(), candidates.end(), [&](const MetaCoupon& a, const MetaCoupon& b) {
ll Ta = a.type_minus_1 + 1;
ll Tb = b.type_minus_1 + 1;
ll Pa = a.p;
ll Pb = b.p;
// Compare Pa / (1 - 1/Ta) vs Pb / (1 - 1/Tb)
// Equivalent to Pa * Ta / (Ta - 1) vs Pb * Tb / (Tb - 1)
// Cross multiply: Pa * Ta * (Tb - 1) < Pb * Tb * (Ta - 1)
return Pa * Ta * (Tb - 1) < Pb * Tb * (Ta - 1);
});
// 4. Execute "Profit" Phase
// Buy everything that strictly increases money.
vector<int> result_indices;
vector<int> counters(4, 0); // Tracks how many of each type we used: counters[1] for Type 2, etc.
ll current_money = A;
for (const auto& c : candidates) {
// We can only take this if it's the NEXT one in its specific sorted list
// The sorted 'candidates' might interleave indices.
// We must ensure we respect the order within the specific type vector.
// ACTUALLY: The user's code blindly takes valid profitable ones.
// But to be valid, we must have bought all cheaper ones of that type first.
// The user's code tracks `cv[mxI]` to ensure we process type-vectors in order.
int t = c.type_minus_1;
int idx = c.vec_idx;
// Only consider the candidate if it is the current head of its type-list
if (idx == counters[t]) {
ll price = v[t][idx].first;
ll mult = t + 1;
// Profit check: (M - P) * T > M => M(T-1) > PT => M > P*T/(T-1)
// Or simply calculate next val
if (current_money < price) break; // Cannot afford
ll next_val = (current_money - price) * mult;
if (next_val > current_money) {
current_money = min(next_val, MAX_VAL);
result_indices.push_back(v[t][idx].second);
counters[t]++;
} else {
// If the "best" available efficiency coupon doesn't increase money,
// the profit phase is over.
break;
}
}
}
// 5. BFS Phase (State Space Search)
// Map State -> Max Money
// State: {count_type2, count_type3, count_type4}
// To use map efficiently, we can encode state or use a tuple/vector.
// User used: {{total_mults, count_type2}, count_type3} -> (count_type4 is derived)
// Let's use counters[1], counters[2], counters[3] as the base offset.
int base_c1 = counters[1];
int base_c2 = counters[2];
int base_c3 = counters[3];
int base_total = base_c1 + base_c2 + base_c3;
// dp key: {c1, c2, c3} relative to base.
// Since map is slow, and depth is small, this is acceptable.
// Key: (u1 << 40) | (u2 << 20) | u3 could work, or just standard map.
map<vector<int>, ll> dp;
map<vector<int>, pair<int, int>> parent; // For reconstruction: {type_added, index}
vector<int> start_state = {0, 0, 0};
dp[start_state] = current_money;
queue<vector<int>> q;
q.push(start_state);
// Track global max coupons
int max_coupons_found = 0;
// We need to store the best state to reconstruct the tail
vector<int> best_state_vector;
// Helper to check Spenders
// Precompute Type 1 prefix sums
vector<ll> type1_prefix;
type1_prefix.push_back(0);
for (auto& p : v[0]) type1_prefix.push_back(type1_prefix.back() + p.first);
auto update_max = [&](ll money, int extra_mults, vector<int> state) {
auto it = upper_bound(type1_prefix.begin(), type1_prefix.end(), money);
int spenders_count = (int)(it - type1_prefix.begin()) - 1;
int total = (int)result_indices.size() + extra_mults + spenders_count;
if (total > max_coupons_found) {
max_coupons_found = total;
best_state_vector = state;
}
};
update_max(current_money, 0, start_state);
while(!q.empty()){
vector<int> s = q.front();
q.pop();
ll cur_m = dp[s];
int u1 = s[0]; // Extra Type 2s used
int u2 = s[1]; // Extra Type 3s used
int u3 = s[2]; // Extra Type 4s used
int total_extra = u1 + u2 + u3;
// Try adding next Type 2
int next_idx1 = base_c1 + u1;
if (next_idx1 < v[1].size()) {
ll p = v[1][next_idx1].first;
if (cur_m >= p) {
ll next_m = min((cur_m - p) * 2, MAX_VAL);
vector<int> next_s = {u1 + 1, u2, u3};
if (dp.find(next_s) == dp.end() || dp[next_s] < next_m) {
dp[next_s] = next_m;
parent[next_s] = {1, v[1][next_idx1].second}; // Store type 1 (index 1 in v)
q.push(next_s);
update_max(next_m, total_extra + 1, next_s);
}
}
}
// Try adding next Type 3
int next_idx2 = base_c2 + u2;
if (next_idx2 < v[2].size()) {
ll p = v[2][next_idx2].first;
if (cur_m >= p) {
ll next_m = min((cur_m - p) * 3, MAX_VAL);
vector<int> next_s = {u1, u2 + 1, u3};
if (dp.find(next_s) == dp.end() || dp[next_s] < next_m) {
dp[next_s] = next_m;
parent[next_s] = {2, v[2][next_idx2].second}; // Store type 2 (index 2 in v)
q.push(next_s);
update_max(next_m, total_extra + 1, next_s);
}
}
}
// Try adding next Type 4
int next_idx3 = base_c3 + u3;
if (next_idx3 < v[3].size()) {
ll p = v[3][next_idx3].first;
if (cur_m >= p) {
ll next_m = min((cur_m - p) * 4, MAX_VAL);
vector<int> next_s = {u1, u2, u3 + 1};
if (dp.find(next_s) == dp.end() || dp[next_s] < next_m) {
dp[next_s] = next_m;
parent[next_s] = {3, v[3][next_idx3].second}; // Store type 3 (index 3 in v)
q.push(next_s);
update_max(next_m, total_extra + 1, next_s);
}
}
}
}
// 6. Reconstruction
// The "result_indices" already has the profit phase coupons.
// We need to append the BFS coupons in reverse order, then append Spenders.
vector<int> bfs_indices;
vector<int> curr = best_state_vector;
while (curr[0] > 0 || curr[1] > 0 || curr[2] > 0) {
pair<int, int> info = parent[curr];
bfs_indices.push_back(info.second);
// Decrement the correct state counter
// info.first is the Type index in v (1, 2, or 3)
// which maps to curr[0], curr[1], curr[2]
curr[info.first - 1]--;
}
// BFS reconstructs last-added first, so reverse it
reverse(bfs_indices.begin(), bfs_indices.end());
result_indices.insert(result_indices.end(), bfs_indices.begin(), bfs_indices.end());
// Add Spenders
ll final_money = dp[best_state_vector];
auto it = upper_bound(type1_prefix.begin(), type1_prefix.end(), final_money);
int cnt_spenders = (int)(it - type1_prefix.begin()) - 1;
for (int i = 0; i < cnt_spenders; ++i) {
result_indices.push_back(v[0][i].second);
}
return result_indices;
}
