#include "festival.h"
#include <algorithm>
#include <climits>
long long Mult(long long a, int t)
{
if (LLONG_MAX / t < a)
return LLONG_MAX;
return a * t;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
int n = P.size();
long long a = A;
std::vector<std::pair<long long, int>> x[4];
for (int i = 0; i < 4; i++)
x[i] = std::vector<std::pair<long long, int>>();
for (int i = 0; i < n; i++)
{
x[T[i] - 1].push_back(std::make_pair(1LL * P[i], i));
}
for (int i = 0; i < 4; i++)
{
std::sort(x[i].begin(), x[i].end());
}
std::vector<int> ans = {};
int j = 0;
while (j < x[1].size() && x[1][j].first * 2 <= a)
{
ans.push_back(x[1][j].second);
a -= x[1][j].first;
a = Mult(a, 2);
j++;
}
for (int i = 1; i < x[0].size(); i++)
x[0][i].first += x[0][i - 1].first;
int max = 0, mj = -1, mi = -1;
{
int l = -1, r = x[0].size();
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (x[0][m].first <= a)
l = m;
else
r = m;
}
max = l + 1;
mj = j - 1;
mi = l;
}
int jj = j;
for (; j < x[1].size(); j++)
{
if (x[1][j].first <= a)
{
a -= x[1][j].first;
a = Mult(a, 2);
int l = -1, r = x[0].size();
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (x[0][m].first <= a)
l = m;
else
r = m;
}
if (j - jj + l + 1 > max)
{
max = j - jj + l + 1;
mj = j;
mi = l;
}
}
else
{
break;
}
}
for (int i = jj; i <= mj; i++)
{
ans.push_back(x[1][i].second);
}
for (int i = 0; i <= mi; i++)
{
ans.push_back(x[0][i].second);
}
return ans;
}
