#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const long long mx = 1e17;
vector<int> cur, best;
int best_type1;
void solve(int pos, long long tokens, int lim, vector<int> a, vector<pair<long long, int>> b, vector<int> p, vector<int> t) {
if (lim == 1 or pos == a.size()) {
int it = lower_bound(b.begin(), b.end(), make_pair(tokens+1, -1)) - b.begin();
if (it + cur.size() > best.size() + best_type1) {
best = cur;
best_type1 = it;
}
return;
}
if (tokens >= p[a[pos]] and lim >= t[a[pos]]) {
cur.pb(a[pos]);
solve(pos + 1, min((tokens - p[a[pos]]) * t[a[pos]], mx), lim, a, b, p, t);
cur.pop_back();
}
solve(pos + 1, tokens, min(lim, 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<long long, int>> b;
for (int i = 0; i < p.size(); i++) {
if (t[i] == 1)
b.pb({p[i], i});
else
a.pb(i);
}
sort(a.begin(), a.end(), [&](int a, int b) {
if (t[a] == t[b])
return p[a] < p[b];
return 1ll * p[a] * t[a] * (t[b] - 1) < 1ll * p[b] * t[b] * (t[a] - 1);
});
sort(b.begin(), b.end());
for (int i = 1; i < b.size(); i++)
b[i].first += b[i-1].first;
vector<int> res;
long long cur = A;
for (int e : a) {
if ((cur-p[e]) * t[e] > cur) {
cur = min(mx, (cur-p[e]) * t[e]);
res.pb(e);
} else
break;
}
a.erase(a.begin(), a.begin() + res.size());
solve(0, cur, 4, a, b, p, t);
for (int e : best)
res.pb(e);
for (int i = 0; i < best_type1; i++)
res.pb(b[i].second);
return res;
}
