// mtlianad chemi kodi araa es
#include<bits/stdc++.h>
using namespace std;
const long long mx = 1e18;
#define pb push_back
vector<int> best, cur;
int best1 = 0;
void go(int ind, long long tok, int tt, vector<int> f, vector<long long> pref, vector<int> p, vector<int> t) {
if (tt == 1 or ind == f.size()) {
auto pos = lower_bound(pref.begin(), pref.end(), tok+1) - pref.begin();
if (pos + cur.size() > best.size() + best1) {
best1 = pos;
best = cur;
}
return;
}
if (tok >= p[f[ind]] and tt >= t[f[ind]]) {
cur.pb(f[ind]);
go(ind+1, min((tok - p[f[ind]]) * t[f[ind]], mx), tt, f, pref, p, t);
cur.pop_back();
}
go(ind+1, tok, min(tt, t[f[ind]]-1), f, pref, p, t);
}
vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
long long tok = a;
vector<int> f, s;
for (int i = 0; i < p.size(); i++) {
if (t[i] == 1)
s.pb(i);
else
f.pb(i);
}
sort(f.begin(), f.end(), [&](int a, int b) {
if (t[a] == t[b])
return p[a] < p[b];
else {
long long A = -p[a] * t[a] * t[b] - p[b] * t[b];
long long B = -p[b] * t[a] * t[b] - p[a] * t[b];
return A > B;
}
});
sort(s.begin(), s.end(), [&](int a, int b) {
return p[a] < p[b];
});
vector<long long> pref(s.size());
if (pref.size() >= 1)
pref[0] = p[s[0]];
for (int i = 1; i < s.size(); i++) {
pref[i] = pref[i-1] + p[s[i]];
}
vector<int> ans;
for (int e : f) {
if ((tok-p[e]) * t[e] > tok) {
ans.pb(e);
tok = min((long long)(tok-p[e]) * t[e], mx);
} else
break;
}
f.erase(f.begin(), f.begin() + int(ans.size()));
go(0, tok, 4, f, pref, p, t);
for (int e : best)
ans.pb(e);
for (int i = 0; i < best1; i++)
ans.pb(s[i]);
return ans;
}
