#include "festival.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ura
{
long long first,second,index;
};
ura vec[200005];
long long spar[200005];
bool cmp(ura a,ura b)
{
if(a.second==b.second)
{
return a.first<b.first;
}
if(a.first==0 || b.first==0)
{
return a.first<b.first;
}
long long val1=1ll*a.first*a.second*b.second+b.first*b.second;
long long val2=1ll*b.first*b.second*a.second+a.first*a.second;
return val1<val2;
}
vector<ura>tip[5];
long long inf=1e16;
int howmany(long long A)
{
int st=1,dr=tip[0].size();
while(st<=dr)
{
int mij=(st+dr)/2;
if(spar[mij]<=A)
{
st=mij+1;
}
else
{
dr=mij-1;
}
}
return st-1;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
int n=P.size();
for(int i=0; i<n; i++)
{
//vec[i].first=P[i];
//vec[i].second=T[i];
//vec[i].index=i;
ura nod;
nod.index=i;
nod.second=T[i];
nod.first=P[i];
tip[T[i]-1].push_back({nod});
}
for(int i=0;i<4;i++)
{
sort(tip[i].begin(),tip[i].end(),cmp);
}
for(int i=1;i<=tip[0].size();i++)
{
spar[i]=spar[i-1]+tip[0][i-1].first;
}
vector<int>rasp;
long long val=A,rez=0,can1=0,can2=0;
for(int p=0;p<=tip[1].size();p++)
{
if(p+howmany(val)>rez)
{
can1=p;
can2=howmany(val);
rez=can1+can2;
}
if(p==tip[1].size() || val<tip[1][p].first)
{
break;
}
val=(val-tip[1][p].first)*2;
val=min(val,inf);
}
for(int i=0;i<can1;i++)
{
rasp.push_back(tip[1][i].index);
}
for(int i=0;i<can2;i++)
{
rasp.push_back(tip[0][i].index);
}
return rasp;
}
