#include <bits/stdc++.h>
struct item {
int64_t i, p, t;
};
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
const int n = P.size();
std::vector<item> a(n);
for (int i = 0; i < n; ++i) {
a[i] = {i, P[i], T[i]};
}
std::sort(a.begin(), a.end(), [&](item i, item j) {
if (i.t != j.t) {
return i.t > j.t;
}
return i.p < j.p;
});
int _n = n;
for (int i = 0; i < n; ++i) {
if (a[i].t == 1) {
_n = i;
break;
}
}
const int lg = 28;
std::vector<int> ans;
// i = number of things chosen from left
for (int i = 0; i <= std::min(_n, lg); ++i) {
int64_t cur = A;
std::vector<int> cur_ans;
bool good = true;
for (int j = 0; j < i; ++j) {
if (cur - a[j].p < 0) {
good = false;
break;
}
cur_ans.push_back(j);
cur = (cur - a[j].p) * a[j].t;
}
if (!good) {
break;
}
for (int j = _n; j < n; ++j) {
if (cur - a[j].p < 0) {
break;
}
cur_ans.push_back(j);
cur = (cur - a[j].p) * a[j].t;
}
if (cur_ans.size() > ans.size()) {
ans = cur_ans;
}
}
return ans;
}
