#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],dp[75][75][75][75];
int pret[75][75][75][75];
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());
for(int a=0;a<koji[1].size();a++)
for(int b=0;b<koji[2].size();b++)
for(int c=0;c<koji[3].size();c++)
for(int d=0;d<koji[4].size();d++)
dp[a][b][c][d]=-inf;
dp[0][0][0][0]=A;
for(int a=0;a<koji[1].size();a++)
for(int b=0;b<koji[2].size();b++)
for(int c=0;c<koji[3].size();c++)
for(int d=0;d<koji[4].size();d++){
if(a!=0 and dp[a][b][c][d]<perform(dp[a-1][b][c][d],{koji[1][a].first,1})){
dp[a][b][c][d]=perform(dp[a-1][b][c][d],{koji[1][a].first,1});
pret[a][b][c][d]=1;
}
if(b!=0 and dp[a][b][c][d]<perform(dp[a][b-1][c][d],{koji[2][b].first,2})){
dp[a][b][c][d]=perform(dp[a][b-1][c][d],{koji[2][b].first,2});
pret[a][b][c][d]=2;
}
if(c!=0 and dp[a][b][c][d]<perform(dp[a][b][c-1][d],{koji[3][c].first,3})){
dp[a][b][c][d]=perform(dp[a][b][c-1][d],{koji[3][c].first,3});
pret[a][b][c][d]=3;
}
if(d!=0 and dp[a][b][c][d]<perform(dp[a][b][c][d-1],{koji[4][d].first,4})){
dp[a][b][c][d]=perform(dp[a][b][c][d-1],{koji[4][d].first,4});
pret[a][b][c][d]=4;
}
}
/*for(int c=0;c<koji[3].size();c++)
for(int d=0;d<koji[4].size();d++){
cout<<c<<" "<<d<<endl;
cout<<endl;
for(int a=0;a<koji[1].size();a++){
for(int b=0;b<koji[2].size();b++)
cout<<dp[a][b][c][d]<<" ";
cout<<endl;
}
cout<<endl;
}*/
int ra=0,rb=0,rc=0,rd=0;
for(int a=0;a<koji[1].size();a++)
for(int b=0;b<koji[2].size();b++)
for(int c=0;c<koji[3].size();c++)
for(int d=0;d<koji[4].size();d++){
if(dp[a][b][c][d]<0)
continue;
if(a+b+c+d>ra+rb+rc+rd){
ra=a;
rb=b;
rc=c;
rd=d;
}
}
vector<int> br;
while(ra>0 or rb>0 or rc>0 or rd>0){
// cout<<ra<<" "<<rb<<" "<<rc<<" "<<rd<<endl;
//cout<<pret[ra][rb][rc][rd]<<endl;
br.push_back(pret[ra][rb][rc][rd]);
switch (pret[ra][rb][rc][rd]){
case 1:
ra--;
break;
case 2:
rb--;
break;
case 3:
rc--;
break;
default:
rd--;
}
}
reverse(br.begin(),br.end());
vector<int> R;
for(int x:br){
R.push_back(koji[x][pok[x]].second);
pok[x]++;
}
return R;
}
