#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
std::vector<signed> max_coupons(signed A, std::vector<signed> P, std::vector<signed> T) {
int _A = A;
vector<pair<int, int>> ones, twos;
for (int i = 0; i < P.size(); i++) {
if (T[i] == 1) ones.push_back({ P[i], i });
else twos.push_back({ P[i], i });
}
ones.push_back({ 0, -1 });
sort(ones.begin(), ones.end());
sort(twos.begin(), twos.end());
int ans = 0, bestI = 0;
for (int i = 1; i < ones.size(); i++) ones[i].first += ones[i - 1].first;
for (int i = 0; i <= twos.size(); i++) {
auto iter = upper_bound(ones.begin(), ones.end(), make_pair(_A, (int)INT_MAX));
iter--;
if (ans < i + (iter - ones.begin())) {
ans = i + (iter - ones.begin());
bestI = i;
}
if (i != twos.size()) _A = 2 * (_A - twos[i].first);
if (_A > 1000000000000000) {
vector<signed> vans;
for (int i = 0; i < twos.size(); i++) vans.push_back(twos[i].second);
for (int i = 1; i < ones.size(); i++) vans.push_back(ones[i].second);
return vans;
}
if (_A < 0) break;
}
vector<signed> vans;
for (int i = 0; i < bestI; i++) vans.push_back(twos[i].second);
for (int i = bestI; i < ans; i++) vans.push_back(ones[i + 1 - bestI].second);
return vans;
}
