#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui __int128_t
#define pb push_back
#define fi first
#define se second
const ll MOD2 = 1e9 + 7;
const ll MOD = 998244353;
const ll MOD3 = 10007;
const ll inf = 1e18;
/********* DEBUG *********/
template<typename T>
struct is_vector : false_type {};
template<typename T, typename A>
struct is_vector<vector<T, A>> : true_type {};
template<typename T>
void print_one(const T& x) {
if constexpr (is_vector<T>::value) {
for (size_t i = 0; i < x.size(); i++) {
cout << x[i];
if (i + 1 < x.size()) cout << ' ';
}
} else {
cout << x;
}
}
template<typename... Args>
void out(const Args&... args) {
bool first = true;
auto print_arg = [&](const auto& v) {
if (!first) cout << ' ';
first = false;
print_one(v);
};
(print_arg(args), ...);
cout << endl;
}
/********* DEBUG *********/
/********* TEMPS *********/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
static inline ll splix(ll x) {
x += 0x9e3779b97f4a7c15ULL;
ll z = x;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
/********* TEMPS *********/
#include "festival.h"
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
ll n = P.size();
ll mx = 1e9;
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [&](int i, int j) {
return 1LL * P[i] * T[i] * (T[j] - 1) < 1LL * P[j] * T[j] * (T[i] - 1);
});
ll m = n-1, LOG = 70;
while (m && T[ord[m]] == 1) m--;
if (T[ord[m]] != 1) m++;
// dp[i][j] = at i, bought j, max coins
// par[i][j], what we last took to get to this state
vector<vector<ll>> dp(n + 1, vector<ll>(LOG, -1)), par(n + 1, vector<ll>(LOG + 1, -1));
dp[0][0] = A;
for (int i = 0; i < m; i++) {
for (int j = 0; j <= LOG; j++) if (dp[i][j] >= 0) {
if (chmax(dp[i+1][j], dp[i][j]))
par[i+1][j] = par[i][j];
if (dp[i][j] >= P[ord[i]]) {
ll nc = min(n * mx, (dp[i][j] - P[ord[i]]) * T[ord[i]]);
if (chmax(dp[i+1][j+1], nc))
par[i+1][j+1] = i;
}
}
}
vector<ll> pref;
for (int i = m; i < n; i++) {
pref.pb(P[ord[i]]);
}
ll k = pref.size();
for (int i = 1; i < k; i++)
pref[i] += pref[i-1];
ll tot = 0, take = -1;
for (int j = m; j >= 0; j--) {
if (dp[m][j] == -1) continue;
ll cur = dp[m][j] + upper_bound(all(pref), dp[m][j]) - pref.begin();
if (chmax(tot, cur))
take = j;
}
vector<int> ans;
ll cur = m, left = dp[m][take];
while (par[cur][take] != -1) {
ans.pb(ord[par[cur][take]]);
cur = par[cur][take];
take--;
}
reverse(all(ans));
for (int i = 0; i < k; i++) {
if (left >= pref[i])
ans.pb(ord[m + i]);
}
return ans;
}
