#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
const long long lim = 1e18;
inline void chmax(long long &a, long long b, int &c, int d)
{
if(a < b){a = b; c = d;}
a = max(a, -1ll); a = min(a, lim);
}
long long dp[75][75];
int trace[75][75];
vector<int> max_coupons(int B, vector<int> P, vector<int> T) {
long long A = B;
//Subtask 4
int n = P.size();
vector<int> order;
for(int i = 0; i < n; i++) order.push_back(i);
sort(order.begin(), order.end(), [&](const int x, const int y){
if(T[x] == T[y]) return P[x] < P[y];
else return (long long)P[x]*T[x]*(T[y]-1) < (long long)P[y]*T[y]*(T[x]-1);
});
memset(dp, -1, sizeof(dp));
memset(trace, -1, sizeof(trace));
dp[0][0] = A;
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++) if(dp[i][j] >= 0){
long long p = P[order[i]], t = T[order[i]];
chmax(dp[i+1][j], dp[i][j], trace[i+1][j], 0);
chmax(dp[i+1][j+1], (dp[i][j]-p)*t, trace[i+1][j+1], 1);
}
}
int r = n, c = 0;
for(int i = 1; i <= n; i++) if(dp[n][i] >= 0) c = i;
vector<int> ans;
while(r > 0){
int val = trace[r][c]; r--;
if(val == 1){c--; ans.push_back(order[r]);}
}
reverse(ans.begin(), ans.end());
return ans;
}
