#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){
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> max_coupons(int A, vector<int> P, vector<int> T) {
//return SolveSubtask5(A,P,T);
return SolveSubtask6(A,P,T);
}
