#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const long long MX = 2000000000000000000;
long long op(long long a, long long num) {
if (num < 0)
return a;
return min(MX, num);
}
vector<int> max_coupons(int ra, vector<int> p, vector<int> t) {
int n = p.size();
long long a = ra;
vector<int> order;
for (int i = 0; i < n; i++)
order.pb(i);
sort(order.begin(), order.end(), [&](int i, int j) {
if (t[i] == t[j]) {
return p[i] < p[j];
} else {
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;
}
});
vector<int> ans, q;
int ind = 0;
for (int e : order) {
while (ind != q.size() and a > p[q[ind]]) {
a = op(a, abs((a-p[q[ind]]) * t[q[ind]]));
ans.pb(q[ind]);
ind++;
}
if (a >= p[e]) {
ans.pb(e);
a = op(a, abs((a-p[e]) * t[e]));
} else {
q.pb(e);
}
}
bool brk = true;
while (ind < q.size()) {
order = q;
q = {};
ind = 0;
for (int e : order) {
while (ind != q.size() and a > p[q[ind]]) {
a = op(a, abs((a-p[q[ind]]) * t[q[ind]]));
ans.pb(q[ind]);
ind++;
brk = false;
}
if (a >= p[e]) {
brk = false;
ans.pb(e);
a = op(a, abs((a-p[e]) * t[e]));
} else {
q.pb(e);
}
}
if (brk)
break;
}
/*
cout<< "\nORDER :\n\t";
for (int e : order) {
cout<< e << ' ';
}
cout<< '\n';
*/
return ans;
}
