#include <bits/stdc++.h>
#include "festival.h"
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std;
const ll MAX=1e16;
vector<pair<ll,ll>> t1,t2,t3,t4;
pair<ll,ll> dp[75][75][75];
ll bs(ll x){
if(t1.size()==0) return 0;
ll l=0,r=t1.size()-1;
while(l<=r){
ll mid=(l+r)/2;
if(t1[mid].fi<=x) l=mid+1;
else r=mid-1;
}
return l;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
ll n=P.size(), a=A;
for(ll i=0; i<n; i++){
if(T[i]==1) t1.pb({P[i],i});
if(T[i]==2) t2.pb({P[i],i});
if(T[i]==3) t3.pb({P[i],i});
if(T[i]==4) t4.pb({P[i],i});
}
sort(t1.begin(),t1.end());
sort(t2.begin(),t2.end());
sort(t3.begin(),t3.end());
sort(t4.begin(),t4.end());
ll r2=0,r3=0,r4=0,r1=bs(a);
ll rsum=r1+r2+r3+r4;
for(ll i=1; i<=t1.size(); i++) t1[i].fi+=t1[i-1].fi;
for(int i=0; i<=t2.size(); i++){
for(int j=0; j<=t3.size(); j++){
for(int z=0; z<=t4.size(); z++){
if(i==0 && j==0 && z==0){
dp[i][j][z]={a,0};
continue;
}
dp[i][j][z]={-1,-1};
if(i>0){
ll r=(dp[i-1][j][z].fi-t2[i-1].fi)*2;
if(r>dp[i][j][z].fi){
dp[i][j][z]={r,2};
}
}
if(j>0){
ll r=(dp[i][j-1][z].fi-t3[j-1].fi)*3;
if(r>dp[i][j][z].fi){
dp[i][j][z]={r,3};
}
}
if(z>0){
ll r=(dp[i][j][z-1].fi-t4[z-1].fi)*4;
if(r>dp[i][j][z].fi){
dp[i][j][z]={r,4};
}
}
dp[i][j][z].fi=min(dp[i][j][z].fi,MAX);
if(dp[i][j][z].fi>=0){
ll cr1=bs(dp[i][j][z].fi);
if(i+j+z+cr1>rsum){
r1=cr1;
r2=i;
r3=j;
r4=z;
rsum=r1+r2+r3+r4;
}
}
}
}
}
vector<int> atb;
ll i=r2,j=r3,z=r4;
while(i>0 || j>0 || z>0){
ll sk=dp[i][j][z].se;
if(sk==2){
i--;
atb.pb(t2[i].se);
}
if(sk==3){
j--;
atb.pb(t3[j].se);
}
if(sk==4){
z--;
atb.pb(t4[z].se);
}
}
reverse(atb.begin(),atb.end());
for(ll i=0; i<r1; i++) atb.pb(t1[i].se);
return atb;
}
