#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int n=P.size();
vector<tuple<ll,int,int,int>>v;
vector<pair<int,int>>w;
for(int i=0;i<n;i++){
if(T[i]!=1)v.push_back({6LL*P[i]*T[i]/(T[i]-1),P[i],T[i],i});
else w.push_back({P[i],i});
}
sort(v.begin(),v.end());
ll a=A;
reverse(v.begin(),v.end());
vector<int>ans1;
while(!v.empty()&&get<0>(v.back())<=6*a){
a=(a-get<1>(v.back()))*get<2>(v.back());
a=min(a,(ll)1e15);
ans1.push_back(get<3>(v.back()));
v.pop_back();
}
reverse(v.begin(),v.end());
sort(w.begin(),w.end());
vector<ll>pref(w.size());
if(!w.empty())pref[0]=w[0].first;
for(int i=1;i<w.size();i++){
pref[i]=pref[i-1]+w[i].first;
}
vector<vector<pair<ll,int>>>dp(v.size()+1,vector<pair<ll,int>>(50,{-1,-1}));
dp[0][0]={a,-1};
pair<int,int>mx={upper_bound(pref.begin(),pref.end(),a)-pref.begin(),0};
for(int i=0;i<v.size();i++){
for(int j=0;j<50;j++){
dp[i][j].first=min(dp[i][j].first,(ll)1e15);
dp[i+1][j]=dp[i][j];
if(j!=0&&dp[i][j-1].first>=get<1>(v[i])){
dp[i+1][j]=max(dp[i][j],{(dp[i][j-1].first-get<1>(v[i]))*get<2>(v[i]),i});
mx=max(mx,{j+upper_bound(pref.begin(),pref.end(),dp[i+1][j].first)-pref.begin(),j});
}
}
}
vector<int>ans;
for(int i=0;i<mx.first-mx.second;i++){
ans.push_back(w[i].second);
}
int temp=v.size();
for(;mx.second>0;mx.second--){
ans.push_back(get<3>(v[dp[temp][mx.second].second]));
temp=dp[temp][mx.second].second;
}
reverse(ans.begin(),ans.end());
for(int i:ans)ans1.push_back(i);
return ans1;
}
