#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
const ll inf = 1e15;
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 = min((A - p[k]) * t[k], inf);
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<vector<ll>> dp(n + 1, vector<ll>(n + 1, -1)); dp[0][0] = A;
vector<vector<bool>> F(n + 1, vector<bool>(n + 1));
for (int i = 1; i <= n; i++){
int k = f[i];
for (int c = 0; c < i; c++){
for (int j = 0; j < i; j++){
if (dp[i - 1][c] >= p[k]){
ll h = (dp[i - 1][c] - p[k]) * t[k];
if (h > dp[i][c + 1]){
dp[i][c + 1] = h;
F[i][c + 1] = 1;
}
}
}
}
for (int c = 0; c <= i; c++) dp[i][c] = max(dp[i][c], dp[i - 1][c]);
}
vector<int> out1;
int c = n;
while (dp[n][c] == -1) c--;
for (int i = n; i > 0; i--){
if (F[i][c]){
out1.pb(f[i]);
c--;
}
}
reverse(out1.begin(), out1.end());
for (int i: out1) out.pb(i);
return out;
}
