#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) const {
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 a = A;
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;
int sz = (int)nr.size();
vector<vector<int>> dp(sz+1, vector<int>(MX+1, -1)); dp[0][0] = a;
vector<vector<char>> vis(sz+1, vector<char>(MX+1, 0));
for(int i = 1; i <= sz; 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]){
vis[i][j] = 1;
dp[i][j] = curr.apply(dp[i-1][j-1]);
}
}
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, 0);
for(int i = 0; i < ones.size(); i++) pref[i+1] = pref[i] + ones[i].p;
auto get = [&](int cnt){
int idx = (int)(upper_bound(pref.begin(), pref.end(), cnt) - pref.begin());
return max(0LL, idx-1);
};
int mx = 0, mxIdx = 0;
for(int i = 0; i <= MX; i++){
if(dp[sz][i] == -1) continue;
if(i + get(dp[sz][i]) > mx){ mx = i + get(dp[sz][i]); mxIdx = i; }
}
vector<int> sol2;
int i = sz, 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(auto &i : sol2) sol.push_back(i);
int res = dp[sz][mxIdx];
for(int i = 0; i < ones.size(); i++){
if(res < ones[i].p) break;
res = ones[i].apply(res);
sol.push_back(ones[i].idx);
}
return sol;
}
