#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(34056237);
ll _ = 0;
vector<int> max_coupons(int A, vector<int> price, vector<int> type) {
ll n = price.size();
vector<vector<pll>> coups(4+1);
for (ll i = 0; i < n; i++) {
coups[type[i]].emplace_back(price[i], i);
}
for (ll i = 1; i <= 4; i++) sort(all(coups[i]));
vector<ll> pref(coups[1].size()+1);
for (ll i = 1; i <= coups[1].size(); i++) {
pref[i] = pref[i-1] + coups[1][i-1].first;
}
vector<ll> rem(coups[2].size()+1, A);
for (ll i = 1; i <= coups[2].size(); i++) {
rem[i] = (rem[i-1] - coups[2][i-1].first) * 2;
if (rem[i] < 0) {
rem.resize(i);
break;
}
if(rem[i] > 1e18) {
rem[i] = 1e18;
}
}
ll mx1 = 0, mx2 = 0;
for (ll t2 = 0; t2 < rem.size(); t2++) {
ll r = rem[t2];
ll t1 = (upper_bound(all(pref), r) - pref.begin()) - 1;
if (t1 + t2 > mx1 + mx2) {
mx1 = t1;
mx2 = t2;
}
}
vector<int> res;
for (ll i = 0; i < mx1; i++) {
res.push_back(coups[1][i].second);
}
for (ll i = 0; i < mx2; i++) {
res.push_back(coups[2][i].second);
}
return res;
}
#ifdef TEST
#include "grader.cpp"
#endif
