/*
-A2 --indent=tab=4 --indent-classes --indent-switches --indent-namespaces --indent-preprocessor -xg -p -xd -H -xj -xe
read all problems
do first-eye problems
read rev order
uhhh dont fail impl
*/
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define re(a, b, c, d) for (int a = b; a <= c; a += d)
#define de(a, b, c, d) for (int a = b; a >= c; a -= d)
#define ms(a, b) memset(a, b, sizeof (a))
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
template <typename T> bool chkmin (T &a, T b) {
return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T &a, T b) {
return (b > a) ? a = b, 1 : 0;
}
using namespace std;
#include "festival.h"
const int N = 2e5 + 5;
vector<int> max_coupons (int A, vector<int> P, vector<int> T) {
int n = P.size();
vector<int> ids (n);
iota (ids.begin(), ids.end(), 0);
sort (ids.begin(), ids.end(), [&] (int a, int b) {
if ((ll)P[a] * T[a] * (T[b] - 1) != (ll)P[b] * T[b] * (T[a] - 1))
return (ll)P[a] * T[a] * (T[b] - 1) < (ll)P[b] * T[b] * (T[a] - 1);
return P[a] < P[b];
});
vector <map <int, pair<ll, bool> > > f (n + 1);
f[0][0] = {A, 0};
re (i, 0, n - 1, 1) {
int p = P[ids[i]], t = T[ids[i]];
for (auto [c, val] : f[i]) {
auto [x, y] = val;
auto& v = f[i + 1][c];
chkmax (v, {x, 0});
if (p <= x) {
auto& u = f[i + 1][c + 1];
chkmax (u, {min ((ll)1e15, (x - p) * t), 1});
}
}
while (f[i + 1].size() >= 50) f[i + 1].erase (f[i + 1].begin());
}
int j = f[n].rbegin() -> F;
vector<int> ans;
de (i, n - 1, 0, 1){
if (!f[i + 1][j].S) continue;
ans.pb (ids[i]);
j--;
}
reverse (ans.begin(), ans.end());
return ans;
}
