#include "festival.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e5+5;
vector<pair<ll,int>> koji[5];
const ll inf=1e18;
int n;
ll cur,pok[5];
ll perform(ll x,pair<ll,ll> sta){
return max(min(inf,(x-sta.f)*sta.s),-inf/10);
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
n=P.size();
for(int i=1;i<=4;i++)
pok[i]=1;
for(int i=1;i<=4;i++)
koji[i].push_back({0,0});
for(int i=0;i<n;i++)
koji[T[i]].push_back({P[i],i});
for(int i=1;i<=4;i++)
sort(koji[i].begin(),koji[i].end());
ll cur=A;
vector<int> R;
while(true){
vector<pair<int,int>> M;
for(int i=1;i<=4;i++)
if(pok[i]<koji[i].size() and cur>=koji[i][pok[i]].f){
M.push_back({koji[i][pok[i]].f,i});
}
/* cout<<M.size()<<endl;
for(auto x:M)
cout<<x.f<<" "<<x.s<<" | ";
cout<<endl;*/
if(M.size()==0)
break;
sort(M.begin(),M.end());
ll bs=-1e18;
int radi=-1;
do{
ll tmp=cur;
for(auto x:M)
tmp=perform(tmp,x);
if(tmp>bs){
bs=tmp;
radi=M[0].second;
}
} while(next_permutation(M.begin(),M.end()));
//cout<<radi<<" "<<pok[radi]<<endl;
cur=perform(cur,{koji[radi][pok[radi]].f,radi});
R.push_back(koji[radi][pok[radi]].s);
pok[radi]++;
}
return R;
}
