#include "festival.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const long long oo = 1LL << 60;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
auto comp = [&](int u, int v)
{
long long costUV = 1LL * P[u] * T[u] * T[v] + 1LL * P[v] * T[v];
long long costVU = 1LL * P[v] * T[v] * T[u] + 1LL * P[u] * T[u];
return costUV < costVU;
};
vector<pair<int, int>> a[5];
int n = size(P);
for (int i = 0; i < n; i++)
a[T[i]].push_back({P[i], i});
for (int i = 1; i <= 4; i++)
sort(begin(a[i]), end(a[i]));
vector<long long> sum1 = {0};
for (auto [x, _] : a[1])
sum1.push_back(sum1.back() + x);
int maxT = *max_element(begin(T), end(T));
// sub 1 + 2 + 3 + 4
if (maxT <= 2 || n <= 70)
{
int best = -1;
vector<int> buy;
for (int i = 0; i <= int(size(a[2])); i++)
for (int j = 0; j <= int(size(a[3])); j++)
for (int k = 0; k <= int(size(a[4])); k++)
{
vector<int> ids;
for (int u = 0; u < i; u++)
ids.push_back(a[2][u].second);
for (int u = 0; u < j; u++)
ids.push_back(a[3][u].second);
for (int u = 0; u < k; u++)
ids.push_back(a[4][u].second);
sort(begin(ids), end(ids), comp);
long long has = A;
for (int i : ids)
{
has = min((has - P[i]) * T[i], oo);
if (has < 0)
break;
}
if (has < 0)
continue;
int u = upper_bound(begin(sum1), end(sum1), has) - begin(sum1) - 1;
int sz = size(ids);
if (u + sz > best)
{
best = u + sz;
buy = {u, i, j, k};
}
}
debug(best, buy);
vector<int> ans;
for (int i = size(buy) - 1; i >= 0; i--)
for (int j = 0; j < buy[i]; j++)
ans.push_back(a[i + 1][j].second);
return ans;
}
// sub 5
vector<int> ids(n);
iota(begin(ids), end(ids), 0);
sort(begin(ids), end(ids), comp);
return ids;
}
