#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
constexpr int64_t inf = 1e15;
vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
int n = p.size();
vector<array<int, 2>> a, b;
for (int i = 0; i < n; i++) {
if (t[i] == 2) {
a.push_back({p[i], i});
} else {
b.push_back({p[i], i});
}
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int m = b.size();
vector<int64_t> pre(m + 1);
for (int i = 0; i < m; i++) {
pre[i + 1] = pre[i] + b[i][0];
}
int64_t x = A;
auto get = [&](int64_t k) {
int l = 0, r = b.size() + 1;
while (l + 1 < r) {
int m = (l + r) / 2;
if (pre[m] <= k) {
l = m;
} else {
r = m;
}
}
return l;
};
int l = 0, r = get(x);
int mx = r;
for (int i = 0; i < a.size(); i++) {
x = (x - a[i][0]) * 2;
if (x < 0) {
break;
}
x = min(x, inf);
int j = get(x);
if (i + j + 1 > mx) {
mx = i + j + 1;
l = i + 1;
r = j;
}
}
vector<int> res;
for (int i = 0; i < l; i++) {
res.push_back(a[i][1]);
}
for (int i = 0; i < r; i++) {
res.push_back(b[i][1]);
}
return res;
}
