#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> max_coupons(int a, vector<int> p, vector<int> t) {
int n = p.size();
vector <vector <pair <int, int>>> adj(5);
for (int i = 0;i < n;i++) {
adj[t[i]].push_back({p[i], i});
}
for (int i = 1;i <= 4;i++) {
sort(adj[i].begin(), adj[i].end());
}
vector <int> pref;
pref.push_back(0);
for (auto x : adj[1]) {
pref.push_back(pref.back() + x.first);
}
int curr = 0;
int fir = 0;
int ans = -1;
int A = a;
for (int i = 0;i <= adj[2].size();i++) {
if (a < 0) break;
int temp = curr + (lower_bound(pref.begin(), pref.end(), a) - pref.begin() - 1);
// cout << a << ' ' << temp << endl;
if (ans < temp) {
ans = temp;
fir = i;
}
if (i == adj[2].size()) break;
a = (a - adj[2][i].first) * 2;
curr++;
}
// cout << endl;
vector <int> res;
for (int i = 0;i < fir;i++) {
res.push_back(adj[2][i].second);
}
for (int i = 0;i < adj[1].size();i++) {
A -= adj[1][i].first;
if (A >= 0) {
res.push_back(adj[1][i].second);
}
}
return res;
}
/*
3 20
4 1
8 2
9 1
*/
