#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
const int MAXN = 200 * 1000 + 17;
const int K = 40;
const ll INF = ll(1000 * 1000 * 1000) * ll(10 * 1000 * 1000);
vector<pair<pll, int>> v;
vector<pair<pll, int>> vec[5];
vector<ll> spref;
vector<pair<pll, int>> el;
int ile (ll x) {
return upper_bound(spref.begin(), spref.end(), x) - spref.begin();
}
bool comp (pair<pll, int> a, pair<pll, int> b) {
return (a.st.nd - 1LL) * (-b.st.st * b.st.nd) < (b.st.nd - 1LL) * (-a.st.st * a.st.nd);
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
vector<int> wyn = {};
vector<int> pref = {};
ll akt = A;
int n = int(P.size());
for (int i = 0; i < n; i ++) {
v.pb({{P[i], T[i]}, i});
}
sort(v.begin(), v.end(), comp);
int j = 0;
for (int i = 0; i < n; i ++) {
if (akt >= v[i].st.st && (akt - v[i].st.st) * v[i].st.nd >= akt) {
akt = (akt - v[i].st.st) * v[i].st.nd;
akt = min(akt, INF);
pref.pb(v[i].nd);
j = i + 1;
} else {
break;
}
}
for (int i = j; i < n; i ++) {
vec[v[i].st.nd].pb(v[i]);
}
sort(vec[1].begin(), vec[1].end());
for (auto x : vec[1]) {
if (spref.empty()) {
spref.pb(x.st.st);
} else {
spref.pb(spref.back() + x.st.st);
}
}
int ile1 = 0;
for (int i = 0; i <= min(K, int(vec[4].size())); i ++) {
for (int j = 0; j <= min(K, int(vec[3].size())); j ++) {
for (int k = 0; k <= min(K, int(vec[2].size())); k ++) {
el.clear();
for (int l = 0; l < i; l ++) {
el.pb(vec[4][l]);
}
for (int l = 0; l < j; l ++) {
el.pb(vec[3][l]);
}
for (int l = 0; l < k; l ++) {
el.pb(vec[2][l]);
}
sort(el.begin(), el.end(), comp);
ll akt2 = akt;
bool ok = 1;
for (auto x : el) {
if (akt2 >= x.st.st) {
akt2 = (akt2 - x.st.st) * x.st.nd;
akt2 = min(akt2, INF);
} else {
ok = 0;
break;
}
}
if (ok) {
if (int(el.size()) + ile(akt2) > int(wyn.size()) + ile1) {
wyn.clear();
for (auto x : el) {
wyn.pb(x.nd);
}
ile1 = ile(akt2);
}
}
}
}
}
for (int i = 0; i < ile1; i ++) {
wyn.pb(vec[1][i].nd);
}
for (auto x : wyn) {
pref.pb(x);
}
return pref;
}
/*int main () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//cout << max_coupons(5, {5}, {1}).size() << "\n";
//for (auto x : max_coupons(10, {6, 5}, {2, 1})) {
//cout << x << "\n";
//}
for (auto x : max_coupons(13, {4, 500, 8, 14}, {1, 3, 3, 4})) {
cout << x << "\n";
}
return 0;
}*/
