#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
ll INF = 2e14;
vector<pair<ll, ll>> v[5];
bool todo=0;
vector<int> fal(vector<ll>in)
{
todo=1;
vector<int>a;
ll i, j;
for(i=1; i<=4; i++)
{
for(j=in[i]; j<sz(v[i]); j++)
{
a.pb(v[i][j].se);
}
}
return a;
}
vector<int> calc(ll t, ll A, vector<ll> in)
{
vector<int> mej, a, b;
if (t == 0)
return mej;
mej = calc(t - 1, A, in);
ll i, j;
bool ag = 1;
while (ag)
{
ag = 0;
for (j = 2; j < t; j++)
{
while (in[j] < sz(v[j]) && (A / j) >= v[j][in[j]].fr)
{
A = A - v[j][in[j]].fr;
A = A * j;
a.pb(v[j][in[j]].se);
in[j]++;
ag = 1;
if (A >= INF)
{
b = fal(in);
for (auto k : b)
{
a.pb(k);
}
return a;
}
}
}
}
for (i = 0; i < sz(v[t]); i++)
{
a.pb(v[t][i].se);
A = A - v[t][i].fr;
if (A < 0)
break;
A = A * t;
if (A >= INF)
{
b = fal(in);
for (auto k : b)
{
a.pb(k);
}
return a;
}
ag = 1;
in[t] = i;
while (ag)
{
ag = 0;
for (j = 2; j < t; j++)
{
while (in[j] < sz(v[j]) && (A / j) >= v[j][in[j]].fr)
{
A = A - v[j][in[j]].fr;
A = A * j;
a.pb(v[j][in[j]].se);
in[j]++;
ag = 1;
if (A >= INF)
{
b = fal(in);
for (auto k : b)
{
a.pb(k);
}
return a;
}
}
}
}
b = calc(t-1, A, in);
if (sz(a) + sz(b) > sz(mej))
{
mej = a;
for (auto k : b)
mej.pb(k);
}
}
return mej;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
ll i, n = sz(P);
vector<ll> in(5, 0);
for (i = 0; i < n; i++)
{
v[T[i]].pb({P[i], i});
}
for (i = 1; i <= 4; i++)
sort(all(v[i]));
return calc(4, A, in);
}
