#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct coupon
{
ll p;
int t;
int idx;
bool operator<(const coupon &other) const { return p < other.p; }
};
vector<int> max_coupons(int A, vector<int> P, vector<int> T)
{
int N = P.size();
vector<coupon> c[5];
for (int i = 0; i < N; i++)
c[T[i]].push_back(coupon {P[i], T[i], i});
for (int i = 1; i <= 4; i++)
sort(c[i].begin(), c[i].end());
int M = c[1].size();
vector<ll> psum(M + 1);
for (int i = 0; i < M; i++)
psum[i + 1] = psum[i] + c[1][i].p;
ll R = A;
int best = -1;
int besti = 0, bestu = 0;
for (int i = 0; i <= ssize(c[2]); i++)
{
int u = upper_bound(psum.begin(), psum.end(), R) - psum.begin() - 1;
int score = i + u;
if (score > best)
{
best = score;
besti = i;
bestu = u;
}
if (i == ssize(c[2]))
break;
R = (R - c[2][i].p) * 2;
R = min(R, LLONG_MAX / 10);
if (R < 0)
break;
}
vector<int> ans;
for (int i = 0; i < besti && i < c[2].size(); i++)
ans.push_back(c[2][i].idx);
for (int i = 0; i < bestu && i < c[1].size(); i++)
ans.push_back(c[1][i].idx);
return ans;
}
