#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int n = (int)P.size();
// coeff[t] = 12 * t / (t-1) for t=2..4
const int coeff[5] = {0, 0, 24, 18, 16};
// ---------- split coupons ----------
vector<pair<long long,int>> cheap; // (price, idx) for T=1
cheap.reserve(n);
struct Booster {
long long key; // p * coeff[t] (fits in int64 for p up to ~1e9)
int p;
int t;
int idx;
};
vector<Booster> boosters;
boosters.reserve(n);
for (int i = 0; i < n; i++) {
int ti = T[i];
int pi = P[i];
if (ti == 1) {
cheap.push_back({(long long)pi, i});
} else {
long long key = 1LL * pi * coeff[ti];
boosters.push_back({key, pi, ti, i});
}
}
// ---------- sort ----------
sort(cheap.begin(), cheap.end(),
[](const auto& a, const auto& b){ return a.first < b.first; });
sort(boosters.begin(), boosters.end(),
[](const Booster& a, const Booster& b){
if (a.key != b.key) return a.key < b.key;
return a.p < b.p;
});
// cheap prefix sums in int64: with P up to 1e9 and N up to 2e5 => sum <= 2e14 fits
vector<long long> cheap_psum(cheap.size() + 1, 0);
vector<int> cheap_idx(cheap.size());
for (size_t i = 0; i < cheap.size(); i++) {
cheap_psum[i + 1] = cheap_psum[i] + cheap[i].first;
cheap_idx[i] = cheap[i].second;
}
auto cheap_cnt_from_token = [&](const cpp_int& tok) -> int {
// If tok is enormous, we can afford all cheap coupons.
static const cpp_int LL_MAX = std::numeric_limits<long long>::max();
if (tok >= LL_MAX) return (int)cheap.size();
long long x = (long long)tok; // safe now
auto it = upper_bound(cheap_psum.begin(), cheap_psum.end(), x);
return int(it - cheap_psum.begin()) - 1; // k s.t. psum[k] <= x
};
// ---------- take all non-decreasing boosters ----------
cpp_int token = A;
vector<int> prefix_ids;
prefix_ids.reserve(boosters.size());
int i = 0, m = (int)boosters.size();
while (i < m) {
const auto &b = boosters[i];
cpp_int p = b.p;
cpp_int t = b.t;
// token*(t-1) >= p*t <=> token >= p*t/(t-1)
if (token * (t - 1) >= p * t) {
prefix_ids.push_back(b.idx);
token = (token - p) * t;
i++;
} else break;
}
// ---------- hard suffix DP ----------
const int K = 61;
int h_len = m - i;
vector<cpp_int> dp(K + 1, cpp_int(-1));
dp[0] = token;
// parent[j][c] = 1 if using hard[j] sets dp[c] at iteration j
vector<vector<uint8_t>> parent(h_len, vector<uint8_t>(K + 1, 0));
for (int j = 0; j < h_len; j++) {
const auto &b = boosters[i + j];
cpp_int p = b.p;
cpp_int t = b.t;
int max_c = min(j + 1, K);
for (int c = max_c; c >= 1; c--) {
if (dp[c - 1] < 0) continue;
cpp_int prev = dp[c - 1];
if (prev >= p) {
cpp_int cand = (prev - p) * t;
if (dp[c] < 0 || cand > dp[c]) {
dp[c] = cand;
parent[j][c] = 1;
}
}
}
}
// ---------- evaluate all possibilities ----------
int best_total = -1;
int best_c = 0;
cpp_int best_token = dp[0];
for (int c = 0; c <= min(K, h_len); c++) {
if (dp[c] < 0) continue;
int cheap_cnt = cheap_cnt_from_token(dp[c]);
int total = i + c + cheap_cnt;
if (total > best_total) {
best_total = total;
best_c = c;
best_token = dp[c];
}
}
// ---------- reconstruct chosen hard subset ----------
vector<int> chosen_hard_pos;
chosen_hard_pos.reserve(best_c);
int need = best_c;
for (int j = h_len - 1; j >= 0 && need > 0; j--) {
if (parent[j][need]) {
chosen_hard_pos.push_back(j);
need--;
}
}
reverse(chosen_hard_pos.begin(), chosen_hard_pos.end());
// ---------- build final answer ----------
vector<int> answer;
answer.reserve(prefix_ids.size() + chosen_hard_pos.size() + cheap.size());
for (int id : prefix_ids) answer.push_back(id);
for (int pos : chosen_hard_pos) answer.push_back(boosters[i + pos].idx);
int cheap_cnt_final = cheap_cnt_from_token(best_token);
for (int k = 0; k < cheap_cnt_final; k++) answer.push_back(cheap_idx[k]);
return answer;
}
