#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=1e17;
vector<pair<int,int>> t1,t2,t3,t4;
int bs(int x){
int l=0,r=t1.size()-1;
while(l<=r){
int 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) {
int n=P.size();
for(int 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());
for(int i=1; i<t1.size(); i++) t1[i].fi+=t1[i-1].fi;
int best=bs(A);
int a1=best,a2=0;
ll c=A;
for(int i=0; i<t2.size(); i++){
c=min(MAX,(c-t2[i].fi)*2);
if(c<0) break;
int pi=bs(c);
if(i+1+pi>best){
best=1+i+pi;
a1=pi;
a2=i+1;
}
}
vector<int> atb;
for(int i=0; i<a2; i++) atb.pb(t2[i].se);
for(int i=0; i<a1; i++) atb.pb(t1[i].se);
return atb;
}
