#include "festival.h"
#include <algorithm>
#include <climits>
long long Mult(long long a, int t)
{
if (LLONG_MAX / t <= a)
return LLONG_MAX - 1;
return a * t;
}
long long Step2(std::vector<std::pair<long long, int>> &P, int &j, long long a, int c, int x)
{
if (j < P.size() && c * P[j].first <= a * (c - 1))
{
return x * P[j].first;
}
return LLONG_MAX;
}
long long Step3(std::vector<std::pair<long long, int>> &P, int &j, long long a, int c, int x)
{
if (j < P.size() && P[j].first < a)
{
return x * P[j].first;
}
return LLONG_MAX;
}
long long Step1(std::vector<std::pair<long long, int>> &P, int &j, long long a, int c, int x)
{
if (j < P.size() && P[j].first < a)
{
return a - (a - P[j].first) * c;
}
return LLONG_MAX;
}
std::vector<std::pair<long long, int>> x[4];
int ind[4];
int kef[4] = {1, 12, 9, 8};
int lim[4] = {1, 32, 20, 16};
std::vector<int> maxans;
int ans[200005];
std::pair<long long, int> Q[200005];
std::vector<int> PP;
std::vector<int> TT;
void Dfs(int j, long long a, int index, int count)
{
if (j == 0)
{
std::vector<std::pair<long long, int>> W;
for (int i = 0; i < count; i++)
{
W.push_back(Q[i]);
}
std::sort(W.begin(), W.end());
for (const std::pair<long long, int> &w : W)
{
if (PP[w.second] > a)
return;
a = (a - PP[w.second]) * TT[w.second];
}
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 (maxans.size() < index + count + l + 1)
{
maxans = std::vector<int>();
for (int i = 0; i < index; i++)
{
maxans.push_back(ans[i]);
}
for (const std::pair<long long, int> &w : W)
{
maxans.push_back(w.second);
}
for (int i = 0; i <= l; i++)
{
maxans.push_back(x[0][i].second);
}
}
return;
}
Dfs(j - 1, a, index, count);
for (int i = ind[j], k = 0; k < lim[j] && i < x[j].size(); i++, k++)
{
Q[count + k] = std::make_pair(1LL * x[j][i].first * kef[j], x[j][i].second);
Dfs(j - 1, a, index, count + k + 1);
}
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
PP = P;
TT = T;
int n = P.size();
long long a = A;
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());
}
int ans_i = 0;
std::fill(ind, ind + 4, 0);
while (true)
{
long long val[] = {LLONG_MAX, Step2(x[1], ind[1], a, 2, kef[1]), Step2(x[2], ind[2], a, 3, kef[2]), Step2(x[3], ind[3], a, 4, kef[3])};
int min = 1;
for (int j = 2; j < 4; j++)
{
if (val[j] < val[min])
min = j;
}
if (val[min] == LLONG_MAX)
break;
ans[ans_i++] = x[min][ind[min]].second;
a = Mult(a - x[min][ind[min]].first, min + 1);
ind[min]++;
}
for (int i = 1; i < x[0].size(); i++)
x[0][i].first += x[0][i - 1].first;
if (x[2].size() > 0 || x[3].size() > 0)
{
Dfs(3, a, ans_i, 0);
}
else
{
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 = ind[1] - 1;
mi = l;
}
for (int j = ind[1]; 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 - ind[1] + l + 2 > max)
{
max = j - ind[1] + l + 2;
mj = j;
mi = l;
}
}
else
{
break;
}
}
maxans = std::vector<int>();
for (int i = 0; i < ans_i; i++)
{
maxans.push_back(ans[i]);
}
for (int i = ind[1]; i <= mj; i++)
{
maxans.push_back(x[1][i].second);
}
for (int i = 0; i <= mi; i++)
{
maxans.push_back(x[0][i].second);
}
}
return maxans;
}
