#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) {
vector<pair<int, int>> a[4];
int n = size(P);
for (int i = 0; i < n; i++)
a[T[i] - 1].push_back({P[i], i});
for (int i = 0; i < 4; i++)
sort(begin(a[i]), end(a[i]));
vector<long long> sum1 = {0};
for (auto [x, _] : a[0])
sum1.push_back(sum1.back() + x);
vector<int> cur(4), fixed;
long long has = A;
while (1)
{
int found = 0;
for (int t = 1; t < 4; t++)
if (cur[t] < size(a[t]))
{
auto [p, id] = a[t][cur[t]];
long long after = min((has - p) * (t + 1), oo);
if (after >= has)
{
has = after;
cur[t]++;
fixed.push_back(id);
found = 1;
break;
}
}
if (!found)
break;
}
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;
};
auto get1 = [&](long long has)
{
return upper_bound(begin(sum1), end(sum1), has) - begin(sum1) - 1;
};
vector<int> ans = {0, int(size(fixed))};
auto updateAns = [&]()
{
int cnt0 = get1(has);
int totalCur = cnt0 + int(size(fixed));
int totalAns = ans[0] + ans[1];
if (totalCur > totalAns)
ans = {cnt0, int(size(fixed))};
};
while (1)
{
updateAns();
int bestT = -1, bestId = -1;
for (int t = 1; t < 4; t++)
if (cur[t] < size(a[t]))
{
auto [p, id] = a[t][cur[t]];
long long after = (has - p) * (t + 1);
if (after < 0)
continue;
if (bestId < 0 || comp(id, bestId))
{
bestT = t;
bestId = id;
}
}
if (bestT < 0)
break;
has = (has - P[bestId]) * (T[bestId]);
fixed.push_back(a[bestT][cur[bestT]++].second);
}
vector<int> coupons;
for (int i = 0; i < ans[1]; i++)
coupons.push_back(fixed[i]);
for (int i = 0; i < ans[0]; i++)
coupons.push_back(a[0][i].second);
return coupons;
}
