#include "festival.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18;
vector<int> cur, best;
int best1;
void solve(int pos, ll tok, int type, vector<int> &a, vector<pair<ll, int> > &b, vector<int> &p, vector<int> &t) {
if(type==1 || pos==a.size())
{
auto it=lower_bound(b.begin(), b.end(), make_pair(tok+1, -1))-b.begin();
if (it+cur.size()>best.size()+best1)
{
best=cur;
best1=it;
}
return ;
}
if(tok>=p[a[pos]] && type>=t[a[pos]]) {
cur.push_back(a[pos]);
solve(pos+1, min((tok-p[a[pos]])*t[a[pos]], INF), type, a, b, p, t);
cur.pop_back();
}
solve(pos + 1, tok, min(type, t[a[pos]] - 1), a, b, p, t);
}
vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
vector<int> a;
vector<pair<ll, int>> b;
int n=p.size();
for(int i=0; i<n; i++)
t[i]!=1 ? a.push_back(i) : b.push_back({p[i], i});
sort(a.begin(), a.end(), [&](int i, int j)
{
if(t[i]==t[j])
return p[i]<p[j];
else
return p[i]*t[i]*(t[j]-1) < p[j]*t[j]*(t[i]-1);
});
sort(b.begin(), b.end());
for(int i=1; i<b.size(); i++)
b[i].first+=b[i-1].first;
vector<int> res;
ll tok = A;
for(auto i: a)
{
if ((tok-p[i])*t[i]>=tok)
{
tok=(tok-p[i])*t[i];
tok=min(tok, (long long)1e15);
res.push_back(i);
} else
break;
}
a.erase(a.begin(), a.begin()+(int)res.size());
solve(0, tok, 4, a, b, p, t);
for(auto i: best)
res.push_back(i);
for(int i = 0; i < best1; i++) {
res.push_back(b[i].second);
}
return res;
}
