#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e16;
int n;
ll tot;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
n = P.size();
tot = A;
vector<pair<ll, int>> v1, v2;
for (int i = 0; i < n; i++) {
if (T[i] == 1) {
v1.push_back({P[i], i});
}
else {
v2.push_back({P[i], i});
}
}
n = v2.size();
int m = v1.size();
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
vector<ll> ps(m, 0);
int best1 = -1, best2 = -1;
for (int i = 0; i < m; i++) {
ps[i] = v1[i].first;
if (i > 0) ps[i] += ps[i-1];
if (ps[i] <= tot) best1 = i;
}
int currAns = best1 + 1;
for (int i = 0; i < n; i++) {
if (tot < v2[i].first) break;
tot = (tot - v2[i].first) * 2;
if (tot > INF) {
best2 = n-1;
best1 = m-1;
break;
}
int lo = 0, hi = m-1;
int id = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (ps[mid] > tot) {
hi = mid-1;
}
else {
lo = mid+1;
id = mid;
}
}
if (id + 1 + i >= currAns) {
currAns = id + 1 + i;
best1 = id;
best2 = i;
}
}
vector<int> ans;
for (int i = 0; i <= best2; i++) ans.push_back(v2[i].second);
for (int i = 0; i <= best1; i++) ans.push_back(v1[i].second);
return ans;
}
