#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<ll,ll>> t1,t2,t3,t4;
ll bs(ll x){
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());
for(ll i=1; i<t1.size(); i++) t1[i].fi+=t1[i-1].fi;
vector<int> atb;
ll p2=0,p3=0,p4=0;
while(p2<t2.size() || p3<t3.size() || p4<t4.size()){
ll g2=(p2<t2.size()?(a-t2[p2].fi)*2-a:-MAX);
ll g3=(p3<t3.size()?(a-t3[p4].fi)*3-a:-MAX);
ll g4=(p4<t4.size()?(a-t4[p4].fi)*4-a:-MAX);
if(p2<t2.size()){
g3*=2;
g4*=2;
}
if(p3<t3.size()){
g2*=3;
g4*=3;
}
if(p4<t4.size()){
g2*=4;
g3*=4;
}
if(g2>=max(g3,g4)){
atb.pb(t2[p2].se);
a=(a-t2[p2].fi)*2;
p2++;
}
else if(g3>=g4){
atb.pb(t3[p3].se);
a=(a-t3[p3].fi)*3;
p3++;
}
else{
atb.pb(t4[p4].se);
a=(a-t4[p4].fi)*4;
p4++;
}
a=min(a,MAX);
}
for(ll i=0; i<t1.size(); i++) atb.pb(t1[i].se);
return atb;
}
