#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];
vector<ll> pref[5];
const ll inf=1e18;
int n;
ll cur;
ll max1(ll x){
int dg=0,gg=koji[1].size()-1,sred,res;
while(dg<=gg){
sred=(dg+gg)/2;
if(pref[1][sred]<=x){
res=sred;
dg=sred+1;
}
else
gg=sred-1;
}
return res;
}
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++)
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 i=1;i<=4;i++){
pref[i].push_back(0);
for(int j=1;j<koji[i].size();j++)
pref[i].push_back(pref[i].back()+koji[i][j].f);
}
int c1=max1(A),c2=0;
cur=A;
for(int i=1;i<koji[2].size();i++){
cur=(cur-koji[2][i].f)*2;
cur=min(cur,inf);
if(cur<0)
break;
int m1=max1(cur);
if(i+m1>c1+c2){
c1=m1;
c2=i;
}
}
vector<int> R;
for(int i=1;i<=c2;i++)
R.push_back(koji[2][i].second);
for(int i=1;i<=c1;i++)
R.push_back(koji[1][i].second);
return R;
}
void reset(){
for(int i=1;i<=4;i++){
koji[i].clear();
pref[i].clear();
}
}
