//#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define ll long long
ll dp[80][80][80][80];
int op[80][80][80][80];
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int N=P.size();
vector<vector<pair<int,int>>> v(5);
ll MX=0;
for(int i=0;i<N;i++){
v[T[i]].pb({P[i],i});
MX+=P[i];
}
for(int i=1;i<5;i++){
sort(v[i].begin(),v[i].end());
}
for(int a=0;a<=v[1].size();a++){
for(int b=0;b<=v[2].size();b++){
for(int c=0;c<=v[3].size();c++){
for(int d=0;d<=v[4].size();d++){
dp[a][b][c][d]=-1;
}
}
}
}
dp[0][0][0][0]=A;
for(int a=0;a<=v[1].size();a++){
for(int b=0;b<=v[2].size();b++){
for(int c=0;c<=v[3].size();c++){
for(int d=0;d<=v[4].size();d++){
if(a!=v[1].size()){
dp[a+1][b][c][d]=max(dp[a+1][b][c][d], dp[a][b][c][d]-v[1][a].ff);
if(dp[a+1][b][c][d]==dp[a][b][c][d]-v[1][a].ff)op[a+1][b][c][d]=1;
dp[a+1][b][c][d]=min(MX,dp[a+1][b][c][d]);
}
if(b!=v[2].size()){
dp[a][b+1][c][d]=max(dp[a][b+1][c][d], (dp[a][b][c][d]-v[2][b].ff)*2);
if(dp[a][b+1][c][d]==(dp[a][b][c][d]-v[2][b].ff)*2)op[a][b+1][c][d]=2;
dp[a][b+1][c][d]=min(MX, dp[a][b+1][c][d]);
}
if(c!=v[3].size()){
dp[a][b][c+1][d]=max(dp[a][b][c+1][d], (dp[a][b][c][d]-v[3][c].ff)*3);
if(dp[a][b][c+1][d]==(dp[a][b][c][d]-v[3][c].ff)*3)op[a][b][c+1][d]=3;
dp[a][b][c+1][d]=min(MX,dp[a][b][c+1][d]);
}
if(d!=v[4].size()){
dp[a][b][c][d+1]=max(dp[a][b][c][d+1], (dp[a][b][c][d]-v[4][d].ff)*4);
if(dp[a][b][c][d+1]==((dp[a][b][c][d]-v[4][d].ff)*4))op[a][b][c][d+1]=4;
dp[a][b][c][d+1]=min(MX,dp[a][b][c][d+1]);
}
}
}
}
}
ll g=0;
vector<int>cur={0,0,0,0};
for(int a=0;a<=v[1].size();a++){
for(int b=0;b<=v[2].size();b++){
for(int c=0;c<=v[3].size();c++){
for(int d=0;d<=v[4].size();d++){
if(dp[a][b][c][d]>=0){
g=max(g,(ll)a+b+c+d);
if(g==(ll)a+b+c+d){
cur={a,b,c,d};
}
}
}
}
}
}
vector<int>f={0,0,0,0};
vector<int>tmp;
while(cur!=f){
int u=op[cur[0]][cur[1]][cur[2]][cur[3]];
cur[u-1]--;
tmp.pb(u);
}
vector<int>ans;
for(int i=1;i<=4;i++)reverse(v[i].begin(),v[i].end());
while(tmp.size()){
ans.pb(v[tmp.back()].back().ss);
v[tmp.back()].pop_back();
tmp.pop_back();
}
return ans;
}
