#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int n;
vector<vector<pii > > v;
vector<signed> max_coupons(signed A, vector<signed> P, vector<signed> T) {
n = P.size();
v.resize(5);
for(int i = 0; i < n; i++) {
v[T[i]].pb(mp(P[i], i));
}
for(int i = 1; i <= 4; i++) {
sort(v[i].begin(), v[i].end());
}
vector<int> vec;
for(pii p : v[1]) {
vec.pb(p.fi);
if(vec.size() > 1) {
vec[vec.size() - 1] += vec[vec.size() - 2];
}
}
int money = A;
pii best = mp((upper_bound(vec.begin(), vec.end(), money) - vec.begin()), 0);
int idx = 0;
for(pii p : v[2]) {
idx++;
if(money < p.fi) {
break;
}
money = (money - p.fi) * 2;
if(money > 1e17) {
money = 1e17;
}
best = max(best, mp(idx + (upper_bound(vec.begin(), vec.end(), money) - vec.begin()), idx));
}
vector<signed> ans;
best.fi -= best.se;
for(int i = 0; i < best.se; i++) {
ans.pb(v[2][i].se);
}
for(int i = 0; i < best.fi; i++) {
ans.pb(v[1][i].se);
}
return ans;
}
