#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second
bool operator < (pil x, pil y){
if (x.ff != y.ff) return x.ff < y.ff;
return x.ss < y.ss;
}
vector<int> max_coupons(int AA, vector<int> p, vector<int> t){
ll A = AA;
int n = (int) p.size();
auto cmp = [&](int i, int j){
return (1LL * p[i] * t[i] * t[j] + 1LL * p[j] * t[j]) < (1LL * p[j] * t[i] * t[j] + 1LL * p[i] * t[i]);
};
vector<int> f;
for (int i = 0; i < n; i++) f.pb(i);
sort(f.begin(), f.end(), cmp);
vector<int> out;
int i = 0;
while (i < n){
int k = f[i];
ll h = (A - p[k]) * t[k];
if (h <= A) break;
A = h;
out.pb(k);
i++;
}
vector<int> fp;
while (i < n) fp.pb(f[i++]);
f = fp;
n = (int) f.size();
f.insert(f.begin(), -1);
vector<pil> dp(n + 1); dp[0] = {0, A};
vector<int> F(n + 1);
for (int i = 1; i <= n; i++){
int k = f[i];
for (int j = 0; j < i; j++){
if (dp[j].ss >= p[k]){
pil nw = {dp[j].ff + 1, (dp[j].ss - p[k]) * t[k]};
if (nw > dp[i]){
dp[i] = nw;
F[i] = j;
}
dp[i] = max(dp[i], {dp[j].ff + 1, (dp[j].ss - p[k]) * t[k]});
}
}
}
pii mx = {0, 0};
int op = 0;
for (int i = 0; i <= n; i++){
if (mx < dp[i]){
mx = dp[i];
op = i;
}
}
vector<int> out1;
while (op > 0){
out1.pb(f[op]);
op = F[op];
}
reverse(out1.begin(), out1.end());
for (int i: out1) out.pb(i);
return out;
}
