#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e16;
struct Coupon {
int p, t, idx;
int apply(int tk){
tk -= p; tk *= t;
if(tk > INF) tk = INF;
if(tk < 0) tk = -1;
return tk;
}
};
vector<signed> max_coupons(signed a, vector<signed> p, vector<signed> t){
int n = (int)p.size();
deque<Coupon> nr, ones;
for(int i = 0; i < n; i++){
if(t[i] == 1) ones.push_back({p[i], t[i], i});
else nr.push_back({p[i], t[i], i});
}
sort(nr.begin(), nr.end(), [&](auto left, auto right){
return left.p * left.t * (right.t - 1) < right.p * right.t * (left.t - 1);
});
sort(ones.begin(), ones.end(), [&](auto left, auto right){
return left.p < right.p;
});
vector<signed> sol;
while(!nr.empty()){
Coupon curr = nr.front();
if(curr.apply(a) < a) break;
a = curr.apply(a);
sol.push_back(curr.idx);
nr.pop_front();
}
const int MX = 100;
vector<vector<int>> dp((int)nr.size()+1, vector<int>(MX+1, -1)); dp[0][0] = a;
vector<vector<bool>> vis((int)nr.size()+1, vector<bool>(MX+1, false));
for(int i = 1; i <= (int)nr.size(); i++){
Coupon curr = nr[i-1];
for(int j = 1; j <= MX; j++){
if(dp[i-1][j-1] == -1) continue;
if(curr.apply(dp[i-1][j-1]) > dp[i][j]){
dp[i][j] = curr.apply(dp[i-1][j-1]);
vis[i][j] = true;
}
}
for(int j = 0; j <= MX; j++){
dp[i][j] = max(dp[i][j], dp[i-1][j]);
}
}
vector<int> pref((int)ones.size()+1);
for(int i = 0; i < (int)ones.size(); i++){
if(i == 0) pref[i] = ones[i].apply(pref[i]);
else {
pref[i] += pref[i-1];
ones[i].apply(pref[i]);
}
}
auto get = [&](int cnt){
return (upper_bound(pref.begin(), pref.end(), cnt) - pref.begin());
};
int mx = 0, mxIdx = 0;
for(int i = 0; i <= MX; i++){
if(dp[nr.size()][i] == -1) continue;
if(i + get(dp[nr.size()][i]) > mx){
mx = get(dp[nr.size()][i]) + i;
mxIdx = i;
}
}
vector<int> sol2;
int i = nr.size(), j = mxIdx;
while(i > 0){
if(j >= 0 && vis[i][j]){
sol2.push_back(nr[i-1].idx);
i--; j--;
} else {
i--;
}
}
reverse(sol2.begin(), sol2.end());
for(int i : sol2) sol.push_back(i);
int res = dp[nr.size()][mxIdx];
for(int i = 0; i < (int)ones.size(); i++){
if(res < ones[i].p) break;
res = ones[i].apply(res);
sol.push_back(ones[i].idx);
}
return sol;
}
