#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
vector<int> R;
int mx=0;
int e=-1;
vector<vector<pair<int, int>>> I(5);
vector<vector<long long>> D(5);
int N = P.size();
for (int i = 0;i < N;i++) {
I[T[i]].push_back({P[i], i});
}
for (int k = 1;k <= 4;k++) {
sort(I[k].begin(), I[k].end());
int S = I[k].size();
D[k].resize(S+1, 0);
}
D[2][0] = A;
for (int i = 1;i <= I[2].size();i++) {
D[2][i] = (D[2][i - 1] - I[2][i-1].first) * 2;
}
for (int i = 1;i <= I[1].size();i++) {
D[1][i] = D[1][i - 1] + I[1][i - 1].first;
}
for (int i = 0;i <= I[2].size();i++) {
if (D[2][i] < 0) { break; }
auto t = upper_bound(D[1].begin(), D[1].end(), D[2][i]);
int c;
if (t != D[1].end()){c = (t - D[1].begin());}
else { c = I[1].size(); }
if (mx < c + i) {
mx = c + i;
e = i;
}
}
for (int i = 0;i < e;i++) {
R.push_back(I[2][i].second);
}
auto t = upper_bound(D[1].begin(), D[1].end(), D[2][e]);
int c;
if (t != D[1].end()) { c = (t - D[1].begin()); }
else { c = I[1].size(); }
for (int i = 0;i < c;i++) {
R.push_back(I[1][i].second);
}
return R;
}
