#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) {
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 and i.t == 1) {
return i.p < j.p;
}
return (j.p + i.p * i.t) * j.t < (i.p + j.p * j.t) * i.t;
});
int64_t A = _a;
const int64_t inf = 1e15;
int cnt_remove = 0;
std::vector<int> ans;
for (int i = 0; i < n; ++i) {
if ((A - a[i].p) * a[i].t < A) {
break;
}
ans.push_back(a[i].i);
A = std::min((A - a[i].p) * a[i].t, inf);
cnt_remove++;
}
for (int i = cnt_remove; i < n; ++i) {
a[i - cnt_remove] = a[i];
}
n -= cnt_remove;
int _n = n;
for (int i = 0; i < n; ++i) {
if (a[i].t == 1) {
_n = i;
break;
}
}
if (_n == 0) {
int64_t cur = A;
for (auto &i : a) {
if (cur - i.p < 0) {
break;
}
cur = (cur - i.p) * i.t;
ans.push_back(i.i);
}
return ans;
}
std::vector<int64_t> psum(n);
if (n != _n) {
psum[_n] = a[_n].p;
}
for (int i = _n + 1; i < n; ++i) {
psum[i] = psum[i - 1] + a[i].p;
}
const int lg = 60;
std::vector dp(_n, std::vector<int64_t>(std::min(_n + 1, lg), -inf));
for (int i = 0; i < _n; ++i) {
for (int j = 0; j <= std::min(_n, lg - 1); ++j) {
if (j == 0) {
dp[i][j] = A;
continue;
}
if (j > i + 1) {
dp[i][j] = -inf;
continue;
}
if (i == 0) {
dp[i][j] = A - a[i].p >= 0 ? (A - a[i].p) * a[i].t : -inf;
continue;
}
dp[i][j] = dp[i - 1][j];
if (dp[i - 1][j - 1] - a[i].p >= 0) {
dp[i][j] = std::max(dp[i][j], (dp[i - 1][j - 1] - a[i].p) * a[i].t);
}
}
for (int j = 0; j <= std::min(_n, lg - 1); ++j) {
dp[i][j] = std::min(dp[i][j], inf);
}
}
int max_ans = 0, corr_j = 0;
for (int j = 0; j <= std::min(_n, lg - 1); ++j) {
if (dp[_n - 1][j] < 0) {
continue;
}
int got = j + std::upper_bound(psum.begin(), psum.end(), dp[_n - 1][j]) - psum.begin() - _n;
if (got > max_ans) {
max_ans = got;
corr_j = j;
}
}
std::vector<int> t_ans;
int i = _n - 1, j = corr_j;
while (i >= 0 and j > 0) {
if (i == 0) {
if (j != 0) {
t_ans.push_back(i);
j--;
}
i--;
continue;
}
if (i != 0 and dp[i - 1][j - 1] - a[i].p >= 0 and (dp[i - 1][j - 1] - a[i].p) * a[i].t > dp[i - 1][j]) {
j--;
t_ans.push_back(i);
}
i--;
}
std::reverse(t_ans.begin(), t_ans.end());
for (int size = max_ans - t_ans.size(), i = 0; i < size; ++i) {
t_ans.push_back(_n + i);
}
for (int &i : t_ans) {
ans.push_back(a[i].i);
}
return ans;
}
