#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200009;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector <pll> t[5];
vector<ll> pref;
vector <ll> HA;
int bs(int A)
{
int l = 0 , r = pref.size() , sro;
while(r - l > 1)
{
sro = (l+r)/2;
if(pref[sro] <= A)l=sro;
else r = sro;
}
return l;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
ll rA = A;
int N = P.size();
for(int i = 0; i < N ; i++)
{
t[T[i]].push_back({P[i],i});
}
for(int j = 1 ; j <= 4 ; j++)sort(t[j].begin() , t[j].end());
pref.push_back(0);
for(auto p : t[1])pref.push_back(pref[pref.size()-1] + p.st);
vector <int> K;
HA.push_back(rA);
int ile = bs(rA) , ind = 0;
for(int i = 1; i <= t[2].size() ; i++)
{
if(rA < t[2][i-1].st)break;
int akt = i;
rA -= t[2][i-1].st;
rA *= 2;
HA.push_back(rA);
akt += bs(rA);
if(rA >= (1e+17))
{
vector <int> temp;
for(auto p : t[2])temp.push_back(p.nd);
for(auto p : t[1])temp.push_back(p.nd);
return temp;
}
if(akt > ile)
{
ile = akt;
ind = i;
}
}
for(int i = 0 ; i < ind; i++)K.push_back(t[2][i].nd);
int I = bs(HA[ind]);
for(int i = 0 ; i < I ; i++)K.push_back(t[1][i].nd);
return {K};
}
