#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];
bool cmp(ura a,ura b)
{
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;
bool check(vector<ura>a,int A)
{
long long val=A;
for(int i=0;i<a.size();i++)
{
if(val>=a[i].first)
{
val=val-a[i].first;
val=val*a[i].second;
val=min(val,inf);
}
else
{
return 0;
}
}
return 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);
}
vector<ura>best;
for(int d1=0; d1<=tip[0].size(); d1++)
{
for(int d2=0; d2<=tip[1].size(); d2++)
{
for(int d3=0; d3<=tip[2].size(); d3++)
{
for(int d4=0; d4<=tip[3].size(); d4++)
{
if(d1+d2+d3+d4>best.size())
{
vector<ura>vec;
for(int i=0; i<d1; i++)
{
vec.push_back(tip[0][i]);
}
for(int i=0; i<d2; i++)
{
vec.push_back(tip[1][i]);
}
for(int i=0; i<d3; i++)
{
vec.push_back(tip[2][i]);
}
for(int i=0; i<d4; i++)
{
vec.push_back(tip[3][i]);
}
sort(vec.begin(),vec.end(),cmp);
if(check(vec,A)==1)
{
best=vec;
}
}
}
}
}
}
vector<int>rasp;
for(int i=0; i<best.size(); i++)
{
rasp.push_back(best[i].index);
}
return rasp;
}
