#include <iostream>
#include <algorithm>
using namespace std;
vector<long long> prefix_sum;
vector<pair<int, int>> coupons_type1;
vector<pair<int, int>> coupons_type2;
int binary_search(long long coins){
int lo = 0, hi = (int)coupons_type1.size() - 1, ans = -1;
while (lo <= hi){
int mid = (lo + hi)/2;
if (prefix_sum[mid] <= coins){
ans = mid;
lo = mid + 1;
}
else{
hi = mid - 1;
}
}
return ans;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T){
for (int i = 0;i < P.size();i++){
if (T[i] == 1){
coupons_type1.push_back({P[i], i});
}
else{
coupons_type2.push_back({P[i], i});
}
}
sort(coupons_type1.begin(), coupons_type1.end());
sort(coupons_type2.begin(), coupons_type2.end());
for (int i = 0;i < coupons_type1.size();i++){
if (i == 0){
prefix_sum.push_back(coupons_type1[i].first);
}
else{
prefix_sum.push_back(prefix_sum[i - 1] + coupons_type1[i].first);
}
}
pair<int, int> num_coupons = {binary_search(A) + 1, 0};
int best_val = binary_search(A) + 1;
long long coins_left = A;
for (int i = 0;i < coupons_type2.size();i++){
if (coins_left < coupons_type2[i].first){
break;
}
else{
coins_left = (coins_left - coupons_type2[i].first) * 2;
if (coins_left > 1000000000000000LL){
coins_left = 1000000000000000LL;
}
}
int binary_search_value = binary_search(coins_left);
if ((i + binary_search_value + 2) > best_val){
best_val = i + binary_search_value + 2;
num_coupons = {binary_search_value + 1, i + 1};
}
}
vector<int> answer;
for (int i = 0;i < num_coupons.second;i++){
answer.push_back(coupons_type2[i].second);
}
for (int i = 0;i < num_coupons.first;i++){
answer.push_back(coupons_type1[i].second);
}
return answer;
}
