#include <bits/stdc++.h>
using namespace std;
using std::vector;
// Minimal non-negative BigInt (base 1e9) with just what we need.
struct BigInt {
static constexpr uint32_t BASE = 1000000000u;
vector<uint32_t> d; // little-endian, d[0] is least significant
BigInt() = default;
BigInt(uint64_t v) { assign(v); }
void assign(uint64_t v) {
d.clear();
if (v == 0) return;
while (v > 0) {
d.push_back(static_cast<uint32_t>(v % BASE));
v /= BASE;
}
}
bool is_zero() const { return d.empty(); }
void trim() {
while (!d.empty() && d.back() == 0) d.pop_back();
}
// Compare with another BigInt: -1, 0, 1
int cmp(const BigInt& other) const {
if (d.size() != other.d.size()) {
return d.size() < other.d.size() ? -1 : 1;
}
for (int i = static_cast<int>(d.size()) - 1; i >= 0; --i) {
if (d[i] != other.d[i]) return d[i] < other.d[i] ? -1 : 1;
}
return 0;
}
// Compare with small uint64 (handy for comparing with int prices)
int cmp_small(uint64_t x) const {
if (d.empty()) return x == 0 ? 0 : -1;
if (d.size() >= 3) return 1; // >= BASE^2 > 1e18 > any uint64 price we compare to
uint64_t val = (d.size() == 2)
? static_cast<uint64_t>(d[0]) + static_cast<uint64_t>(d[1]) * BASE
: static_cast<uint64_t>(d[0]);
if (val < x) return -1;
if (val > x) return 1;
return 0;
}
// x += y
void add(const BigInt& y) {
size_t n = std::max(d.size(), y.d.size());
d.resize(n, 0);
uint64_t carry = 0;
for (size_t i = 0; i < n; ++i) {
uint64_t sum = carry + d[i] + (i < y.d.size() ? y.d[i] : 0u);
d[i] = static_cast<uint32_t>(sum % BASE);
carry = sum / BASE;
}
if (carry) d.push_back(static_cast<uint32_t>(carry));
}
// x += small
void add_small(uint64_t x) {
uint64_t carry = x;
size_t i = 0;
while (carry > 0) {
if (i == d.size()) d.push_back(0);
uint64_t sum = static_cast<uint64_t>(d[i]) + carry;
d[i] = static_cast<uint32_t>(sum % BASE);
carry = sum / BASE;
++i;
}
}
// assume x >= y
void sub(const BigInt& y) {
uint64_t borrow = 0;
for (size_t i = 0; i < d.size(); ++i) {
uint64_t yi = (i < y.d.size() ? y.d[i] : 0u);
uint64_t cur = static_cast<uint64_t>(d[i]);
uint64_t sub_v = yi + borrow;
if (cur >= sub_v) {
d[i] = static_cast<uint32_t>(cur - sub_v);
borrow = 0;
} else {
d[i] = static_cast<uint32_t>(cur + BASE - sub_v);
borrow = 1;
}
}
trim();
}
// assume x >= small
void sub_small(uint64_t x) {
uint64_t carry = x;
size_t i = 0;
while (carry > 0) {
uint64_t cur = (i < d.size() ? d[i] : 0u);
uint64_t xi = carry % BASE;
carry /= BASE;
if (cur >= xi) {
d[i] = static_cast<uint32_t>(cur - xi);
} else {
d[i] = static_cast<uint32_t>(cur + BASE - xi);
// Borrow 1 from next chunk
carry += 1;
}
++i;
}
trim();
}
// x *= small (small <= 4 in our use)
void mul_small(uint32_t m) {
if (is_zero() || m == 1) return;
if (m == 0) { d.clear(); return; }
uint64_t carry = 0;
for (size_t i = 0; i < d.size(); ++i) {
uint64_t prod = static_cast<uint64_t>(d[i]) * m + carry;
d[i] = static_cast<uint32_t>(prod % BASE);
carry = prod / BASE;
}
if (carry) d.push_back(static_cast<uint32_t>(carry));
}
};
// Convenience comparisons for BigInt
static inline bool operator<(const BigInt& a, const BigInt& b) { return a.cmp(b) < 0; }
static inline bool operator<=(const BigInt& a, const BigInt& b) { return a.cmp(b) <= 0; }
static inline bool operator>(const BigInt& a, const BigInt& b) { return a.cmp(b) > 0; }
static inline bool operator>=(const BigInt& a, const BigInt& b) { return a.cmp(b) >= 0; }
static inline bool operator==(const BigInt& a, const BigInt& b) { return a.cmp(b) == 0; }
static inline bool operator!=(const BigInt& a, const BigInt& b) { return a.cmp(b) != 0; }
// Main function as requested
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
struct Item {
int idx;
int price; // P
int mult; // T >= 2
int64_t k_num; // P * T
int k_den; // T - 1
};
const int n = static_cast<int>(P.size());
vector<Item> boosters;
vector<std::pair<int,int>> plains; // (price, idx) for T==1
boosters.reserve(n);
plains.reserve(n);
for (int i = 0; i < n; ++i) {
if (T[i] == 1) {
plains.emplace_back(P[i], i);
} else {
Item it;
it.idx = i;
it.price = P[i];
it.mult = T[i];
it.k_num = static_cast<int64_t>(P[i]) * static_cast<int64_t>(T[i]); // safe: P is int
it.k_den = T[i] - 1;
boosters.push_back(it);
}
}
// Comparator for K (exact via cross-multiplication)
auto keyLessItem = [&](const Item& a, const Item& b) -> bool {
// Compare a.k_num/a.k_den < b.k_num/b.k_den <=> a.k_num*b.k_den < b.k_num*a.k_den
int64_t left = a.k_num * b.k_den;
int64_t right = b.k_num * a.k_den;
if (left != right) return left < right;
if (a.price != b.price) return a.price < b.price;
return a.idx < b.idx;
};
// Coordinate compress booster prices
vector<int> uniquePrices;
uniquePrices.reserve(boosters.size());
for (auto &it : boosters) uniquePrices.push_back(it.price);
std::sort(uniquePrices.begin(), uniquePrices.end());
uniquePrices.erase(std::unique(uniquePrices.begin(), uniquePrices.end()), uniquePrices.end());
const int M = static_cast<int>(uniquePrices.size());
auto priceToCoord = [&](int price) -> int {
return static_cast<int>(std::lower_bound(uniquePrices.begin(), uniquePrices.end(), price) - uniquePrices.begin());
};
// Group boosters by price coordinate
vector<vector<int>> groups(M); // holds indices into boosters
for (int i = 0; i < static_cast<int>(boosters.size()); ++i) {
int d = priceToCoord(boosters[i].price);
groups[d].push_back(i);
}
// Sort each price group by K asc, then idx
for (int d = 0; d < M; ++d) {
std::sort(groups[d].begin(), groups[d].end(), [&](int i, int j){
const Item& a = boosters[i];
const Item& b = boosters[j];
return keyLessItem(a, b);
});
}
vector<int> ptr(M, 0); // next candidate in each price group
// Segment tree over price coords, each node stores best item index by K
struct SegTree {
int n;
vector<int> t; // stores index into boosters, or -1
const vector<vector<int>>* groups;
vector<int>* ptr;
const vector<Item>* items;
SegTree(int n_, const vector<vector<int>>* groups_, vector<int>* ptr_, const vector<Item>* items_)
: n(n_), t(n_ ? 4*n_ : 0, -1), groups(groups_), ptr(ptr_), items(items_) {}
// Return the better index by K
int pick(int a, int b) const {
if (a == -1) return b;
if (b == -1) return a;
const Item& ia = (*items)[a];
const Item& ib = (*items)[b];
int64_t left = ia.k_num * ib.k_den;
int64_t right = ib.k_num * ia.k_den;
if (left != right) return (left < right) ? a : b;
if (ia.price != ib.price) return (ia.price < ib.price) ? a : b;
return (ia.idx < ib.idx) ? a : b;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
int d = tl;
int candidate = -1;
if ((*ptr)[d] < static_cast<int>((*groups)[d].size())) {
candidate = (*groups)[d][(*ptr)[d]];
}
t[v] = candidate;
} else {
int tm = (tl + tr) >> 1;
build(v<<1, tl, tm);
build(v<<1|1, tm+1, tr);
t[v] = pick(t[v<<1], t[v<<1|1]);
}
}
void build() {
if (n > 0) build(1, 0, n-1);
}
void update(int v, int tl, int tr, int pos) {
if (tl == tr) {
int d = tl;
int candidate = -1;
if ((*ptr)[d] < static_cast<int>((*groups)[d].size())) {
candidate = (*groups)[d][(*ptr)[d]];
}
t[v] = candidate;
} else {
int tm = (tl + tr) >> 1;
if (pos <= tm) update(v<<1, tl, tm, pos);
else update(v<<1|1, tm+1, tr, pos);
t[v] = pick(t[v<<1], t[v<<1|1]);
}
}
void update(int pos) {
if (n > 0) update(1, 0, n-1, pos);
}
// Query best item index in [l..r]
int query(int v, int tl, int tr, int l, int r) const {
if (l > r) return -1;
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) >> 1;
int left = query(v<<1, tl, tm, l, std::min(r, tm));
int right = query(v<<1|1, tm+1, tr, std::max(l, tm+1), r);
return pick(left, right);
}
int query(int l, int r) const {
if (n == 0 || l > r) return -1;
return query(1, 0, n-1, l, r);
}
};
SegTree st(M, &groups, &ptr, &boosters);
st.build();
auto lastAffordableCoord = [&](const BigInt& tokens) -> int {
// largest index d with uniquePrices[d] <= tokens, or -1 if none
int lo = 0, hi = M;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (tokens.cmp_small(static_cast<uint64_t>(uniquePrices[mid])) >= 0) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo - 1;
};
// 1) Build greedy booster sequence, recording tokens after each prefix
BigInt tokens(static_cast<uint64_t>(A));
vector<BigInt> tokens_after;
tokens_after.push_back(tokens);
vector<int> booster_seq;
while (true) {
int r = lastAffordableCoord(tokens);
if (r < 0) break;
int id = st.query(0, r);
if (id == -1) break;
const Item& it = boosters[id];
// Buy it: tokens = T * (tokens - P)
// Sanity: tokens >= price by construction
tokens.sub_small(static_cast<uint64_t>(it.price));
tokens.mul_small(static_cast<uint32_t>(it.mult));
booster_seq.push_back(it.idx);
tokens_after.push_back(tokens);
// Consume it from its price group
int d = priceToCoord(it.price);
++ptr[d];
st.update(d);
}
// 2) Handle T=1: sort by price asc then idx
std::sort(plains.begin(), plains.end()); // pair sorts by (price, idx)
int M1 = static_cast<int>(plains.size());
vector<BigInt> pref; // prefix sums of T=1 prices
pref.reserve(M1 + 1);
pref.emplace_back(0u);
for (auto &q : plains) {
BigInt next = pref.back();
next.add_small(static_cast<uint64_t>(q.first));
pref.push_back(std::move(next));
}
auto max_plains_with = [&](const BigInt& x) -> int {
// largest m with pref[m] <= x
int lo = 0, hi = M1;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (pref[mid] <= x) lo = mid;
else hi = mid - 1;
}
return lo;
};
// 3) Choose best prefix length of boosters
int best_total = -1;
int best_k = 0;
for (int k = 0; k < static_cast<int>(tokens_after.size()); ++k) {
int m = max_plains_with(tokens_after[k]);
int total = k + m;
if (total > best_total) {
best_total = total;
best_k = k;
}
}
// 4) Construct final order: first best_k boosters, then m plains
vector<int> order;
order.reserve(std::max(0, best_total));
for (int i = 0; i < best_k; ++i) order.push_back(booster_seq[i]);
BigInt tok = tokens_after[best_k];
for (int i = 0; i < M1; ++i) {
if (tok.cmp_small(static_cast<uint64_t>(plains[i].first)) >= 0) {
tok.sub_small(static_cast<uint64_t>(plains[i].first));
order.push_back(plains[i].second);
} else {
break;
}
}
return order;
}
