#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<array<int, 3>> pt(n);
for (int i = 0; i < n; i++) {
pt[i] = {p[i], t[i], i};
}
vector<vector<pair<int, int>>> byt(5);
for (int i = 0; i < n; i++) {
byt[pt[i][1]].emplace_back(pt[i][0], i);
}
for (int i = 1; i <= 4; i++) {
sort(byt[i].begin(), byt[i].end());
}
vector<int> order;
long long awa = a;
vector<int> pp(5);
while (pp[1] < byt[1].size() || pp[2] < byt[2].size() || pp[3] < byt[3].size() || pp[4] < byt[4].size()) {
vector<int> valid;
for (int i = 1; i <= 4; i++) {
if (pp[i] < byt[i].size() && awa >= byt[i][pp[i]].first) {
valid.push_back(i);
}
}
if (valid.size() == 0) {
break;
}
if (valid.size() == 1) {
awa = static_cast<long long>(valid[0]) * static_cast<long long>(awa - byt[valid[0]][pp[valid[0]]].first);
if (awa > static_cast<long long>(1e15)) {
awa = static_cast<long long>(1e15);
}
order.emplace_back(byt[valid[0]][pp[valid[0]]].second);
++pp[valid[0]];
} else {
pair<int, int> best = make_pair(byt[valid[0]][pp[valid[0]]].first, valid[0]);
int id = 0;
for (int i = 1; i < valid.size(); i++) {
pair<int, int> now = make_pair(byt[valid[i]][pp[valid[i]]].first, valid[i]);
if (static_cast<long long>(now.first) * static_cast<long long>(now.second) * static_cast<long long>(best.second - 1) < static_cast<long long>(best.first) * static_cast<long long>(best.second) * static_cast<long long>(now.second - 1)) {
id = i;
best = now;
}
}
awa = static_cast<long long>(valid[id]) * static_cast<long long>(awa - byt[valid[id]][pp[valid[id]]].first);
if (awa > static_cast<long long>(1e15)) {
awa = static_cast<long long>(1e15);
}
order.emplace_back(byt[valid[id]][pp[valid[id]]].second);
++pp[valid[id]];
}
}
return order;*/
vector<pair<int, int>> ones, twos;
for (int i = 0; i < n; i++) {
if (t[i] == 1) {
ones.push_back(make_pair(p[i], i));
} else {
twos.push_back(make_pair(p[i], i));
}
}
long long awa = a;
sort(twos.begin(), twos.end());
sort(ones.begin(), ones.end());
int mx = 0, id = -1;
long long rn = 0;
for (int i = 0; i < ones.size(); i++) {
if (rn + ones[i].first <= a) {
mx++;
rn += ones[i].first;
}
}
vector<long long> pref(ones.size() + 1);
for (int i = 1; i <= ones.size(); i++) {
pref[i] = pref[i - 1] + ones[i - 1].first;
}
vector<int> order;
for (int i = 0; i < twos.size(); i++) {
if (awa < twos[i].first) {
break;
} else {
awa = static_cast<long long>(2) * static_cast<long long>(awa - twos[i].first);
if (awa > static_cast<long long>(1e15)) {
awa = static_cast<long long>(1e15);
}
int low = 0, high = ones.size(), idx = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (awa >= pref[mid]) {
idx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (mx < i + idx + 2) {
mx = i + idx + 2;
id = i;
}
}
}
long long awa2 = a;
for (int i = 0; i <= id; i++) {
awa2 = static_cast<long long>(2) * static_cast<long long>(awa2 - twos[i].first);
if (awa2 > static_cast<long long>(1e15)) {
awa2 = static_cast<long long>(1e15);
}
order.emplace_back(twos[i].second);
}
for (int i = 0; i < ones.size(); i++) {
if (awa2 >= ones[i].first) {
awa2 -= ones[i].first;
order.emplace_back(ones[i].second);
}
}
return order;
}
