#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
vector<int> SolveSubtask5(int A,vector<int> P,vector<int> T){
int n=P.size();
vector<int> ans(n);
iota(ans.begin(),ans.end(),0);
sort(ans.begin(),ans.end(),[&](int i,int j){
if(T[i]!=3 && T[j]!=3)return make_pair(-T[i],P[i])<make_pair(-T[j],P[j]);
return (ll)-P[i]*T[i]*T[j]-(ll)P[j]*T[j]>(ll)-P[j]*T[j]*T[i]-(ll)P[i]*T[i];
});
return ans;
}
vector<int> SolveSubtask6(ll A,vector<int> P,vector<int> T){
int n=P.size();
array<vector<int>,5> cand;
for(int i=0;i<n;i++){
cand[T[i]].pb(i);
}
for(int i=1;i<=4;i++){
sort(cand[i].begin(),cand[i].end(),[&](int i,int j){return P[i]>P[j];});
}
vector<int> ans;
while(true){
int bestT=0;
ll left=-1;
for(int i=1;i<=4;i++){
if(cand[i].size()){
int j=cand[i].back();
ll now=(ll)(A-P[j])*T[j];
if(now>=left){
bestT=i;
left=now;
}
}
}
if(bestT==0)break;
ans.pb(cand[bestT].back());
cand[bestT].pop_back();
A=left;
}
return ans;
}
vector<int> Solve(ll A,vector<int> P,vector<int> T){
int n=P.size();
vector<int> ord(n);
iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int i,int j){
return (ll)-P[i]*T[i]*T[j]-(ll)P[j]*T[j]>(ll)-P[j]*T[j]*T[i]-(ll)P[i]*T[i];
});
vector<int> ans;
for(int i:ord){
if(A>=P[i]){
ans.pb(i);
A=(A-P[i])*T[i];
}
}
return ans;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
return SolveSubtask5(A,P,T);
//return SolveSubtask6(A,P,T);
//return Solve(A,P,T);
}
