#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> ans;
void solve(int ind, int &a, vector<int> &order, vector<int> &p, vector<int> &t) {
if (ind >= order.size())
return;
if (a >= p[order[ind]]) {
a = (a-p[order[ind]]) * t[order[ind]];
ans.pb(order[ind]);
solve(ind+1, a, order, p, t);
} else {
solve(ind+1, a, order, p, t);
if (a >= p[order[ind]]) {
a = (a-p[order[ind]]) * t[order[ind]];
ans.pb(order[ind]);
}
}
}
vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
int n = p.size();
vector<int> order;
for (int i = 0; i < n; i++)
order.pb(i);
sort(order.begin(), order.end(), [&](int i, int j) {
long long A = -p[i]*t[i]*t[j] - p[j]*t[j];
long long B = -p[j]*t[i]*t[j] - p[i]*t[i];
if (A == B)
return p[i] < p[j];
return A > B;
});
solve(0, a, order, p, t);
return ans;
}
