#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e15;
ll lg = 60;
vector<int> max_coupons(int A, vector<int> PP, vector<int> TT) {
vector<ll> P(PP.begin(), PP.end()), T(TT.begin(), TT.end());
ll n = P.size(), AA = A;
vector<int> ind, ans, is1, initans, sind(n), took(n, 0);
iota(sind.begin(), sind.end(), 0LL);
sort(sind.begin(), sind.end(), [&](int i, int j){return P[i]*T[i]*T[j] + P[j]*T[j] < P[j]*T[j]*T[i] + P[i]*T[i];});
for (ll i : sind) {
if ((AA - P[i]) * T[i] >= AA) {
took[i] = true;
initans.push_back(i);
AA = min(INF, T[i]*(AA - P[i]));
}
}
for (int i = 0; i < n; i++) {
if (T[i]==1) is1.push_back(i);
else if (!took[i]) ind.push_back(i);
}
sort(ind.begin(), ind.end(), [&](int i, int j){return P[i]*T[i]*T[j] + P[j]*T[j] < P[j]*T[j]*T[i] + P[i]*T[i];});
sort(is1.begin(), is1.end(), [&](int i, int j){return P[i] < P[j];});
ll m = ind.size();
vector<vector<bool>> bought(m+1, vector<bool>(lg, 0));
vector<vector<ll>> dp(m+1, vector<ll>(lg, -INF));
vector<vector<array<ll, 2>>> par(m+1, vector<array<ll, 2>>(lg, {-1, -1}));
for (ll i = 0; i <= m; i++) for (ll j = 0; j < min(i+1, lg); j++) {
if (j==0) dp[i][j] = AA;
else {
dp[i][j] = dp[i-1][j];
par[i][j] = {i-1, j};
if (dp[i-1][j-1] >= P[ind[i-1]] && (dp[i-1][j-1] - P[ind[i-1]])*T[ind[i-1]] >= dp[i][j]) {
dp[i][j] = (dp[i-1][j-1] - P[ind[i-1]])*T[ind[i-1]];
par[i][j] = {i-1, j-1};
bought[i][j] = true;
}
}
dp[i][j] = min(dp[i][j], INF);
}
for (ll j = 0; j < lg; j++) {
if (dp[m][j] >= 0) {
vector<int> tempans;
ll x = m, y = j;
while (x > 0 && y > 0) {
if (bought[x][y]) tempans.push_back(ind[x-1]);
auto p = par[x][y];
x = p[0], y = p[1];
}
reverse(tempans.begin(), tempans.end());
ll fin = dp[m][j];
for (ll i : is1) if (fin >= P[i]) {
tempans.push_back(i);
fin -= P[i];
}
if (tempans.size() > ans.size()) ans = tempans;
}
}
for (int i : ans) initans.push_back(i);
return initans;
}
