#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
#define pb push_back
#define ll long long
ll tot;
struct info{
ll p,t,i;
friend bool operator<(info a,info b){
ll sc1=(tot-a.p)*a.t;
sc1=(sc1-b.p)*b.t;
ll sc2=(tot-b.p)*b.t;
sc2=(sc2-a.p)*a.t;
return sc1>sc2;
}
};
ll pref[200005],sz;
int score(ll a){
if(sz==0 || a<pref[0])return 0;
if(a>=pref[sz-1])return sz;
int l=0,r=sz-1;
while(l<r){
int mid=(l+r+1)/2;
if(pref[mid]<=a)l=mid;
else r=mid-1;
}
if(pref[l]>a)l--;
return l+1;
}
int pos(ll A, std::vector<int> P[5]) {
vector<info> v2;
for(int i=0;i<P[2].size();i++)v2.pb({P[2][i],2LL,i});
for(int i=0;i<P[3].size();i++)v2.pb({P[3][i],3LL,i});
for(int i=0;i<P[4].size();i++)v2.pb({P[4][i],4LL,i});
sort(v2.begin(),v2.end());
for(auto j:v2){
A=(A-j.p)*j.t;
if(A<0)return 0;
A=min(A,(long long)1e17);
}
return P[2].size()+P[3].size()+P[4].size()+score(A);
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
tot=A;
vector<pair<ll,ll>> v[5];
vector<info> v2;
for(int i=0;i<T.size();i++){
v[T[i]].pb({P[i],i});
}
for(int i=0;i<5;i++){
if(!v[i].empty())sort(v[i].begin(),v[i].end());
}
sz=(int)v[1].size();
for(int i=0;i<sz;i++){
pref[i]=v[1][i].first;
if(i>0)pref[i]+=pref[i-1];
}
vector<int> p[5];
vector<int> sol;
for(int j=0;j<=v[2].size();j++) {
for (int k = 0; k <= v[3].size(); k++) {
for (int l = 0; l <= v[4].size(); l++) {
if (pos(A, p)>sol.size()) {
sol.clear();
for(int i=0;i<j;i++)sol.pb(v[2][i].second);
for(int i=0;i<k;i++)sol.pb(v[3][i].second);
for(int i=0;i<l;i++)sol.pb(v[4][i].second);
for(int i=0;i<pos(A,p)-j-k-l;i++)sol.pb(v[1][i].second);
}
if (l != v[4].size()) p[4].pb(v[4][l].first);
}
p[4].clear();
if (k != v[3].size()) p[3].pb(v[3][k].first);
}
p[3].clear();
if (j != v[2].size())p[2].pb(v[2][j].first);
}
return sol;
}
