#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
using i128 = __int128_t;
using p2 = pair<i64, i64>;
using p3 = tuple<i64, i64, i64>;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
i32 n = P.size();
vector<vector<p2>> v(5);
for (i32 i = 0; i < n; i++) {
v[T[i]].push_back({P[i], i});
}
for (i32 i = 1; i < 5; i++) sort(v[i].begin(), v[i].end());
vector<int> res;
for (i32 i1 = v[1].size(); i1 <= v[1].size(); i1++) {
for (i32 i2 = v[2].size(); i2 <= v[2].size(); i2++) {
for (i32 i3 = v[3].size(); i3 <= v[3].size(); i3++) {
for (i32 i4 = v[4].size(); i4 <= v[4].size(); i4++) {
vector<p3> vv;
for (i32 i = 0; i < i1; i++) vv.push_back({v[1][i].first, 1, v[1][i].second});
for (i32 i = 0; i < i2; i++) vv.push_back({v[2][i].first, 2, v[2][i].second});
for (i32 i = 0; i < i3; i++) vv.push_back({v[3][i].first, 3, v[3][i].second});
for (i32 i = 0; i < i4; i++) vv.push_back({v[4][i].first, 4, v[4][i].second});
sort(vv.begin(), vv.end(), [](p3 a, p3 b){
auto [p1, t1, i] = a;
auto [p2, t2, j] = b;
i64 x = p1 * t1 * t2 + p2 * t2;
i64 y = p2 * t1 * t2 + p1 * t1;
return x < y;
});
bool ok = true;
i64 sum = A;
vector<i32> vi;
for (auto [p1, t1, i] : vv) {
sum = (sum - p1) * t1;
vi.push_back(i);
ok &= sum >= 0;
if (!ok) break;
if (sum >= 1e16) {
break;
}
}
assert((sum >= 0) == ok);
/*
if ((sum >= 0) != ok) {
cout << vv.size() << ": ";
for (auto [p1, t1, i] : vv) {
cout << "[" << p1 << " " << t1 << "] ";
}
cout << endl;
sum = A;
for (auto [p1, t1, i] : vv) {
sum = (sum - p1) * t1;
cout << sum << " ";
}
cout << "!" << endl;
}
assert((sum >= 0) == ok);
*/
if (sum < 0) continue;
if (vi.size() > res.size()) {
res = vi;
}
}
}
}
}
return res;
}
