#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e15;
vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
int n = p.size();
vector<vector<pair<int, int>>> byt(5);
for (int i = 0; i < n; i++) {
byt[t[i]].emplace_back(p[i], i);
}
for (int i = 1; i <= 4; i++) {
sort(byt[i].begin(), byt[i].end());
}
vector<int> order;
long long awa = a;
int s1 = byt[1].size(), s2 = byt[2].size(), s3 = byt[3].size(), s4 = byt[4].size();
vector<vector<vector<vector<long long>>>> dp(s1 + 1, vector<vector<vector<long long>>>(s2 + 1, vector<vector<long long>>(s3 + 1, vector<long long>(s4 + 1, -1))));
dp[0][0][0][0] = a;
for (int i = 0; i <= s1; i++) {
for (int j = 0; j <= s2; j++) {
for (int k = 0; k <= s3; k++) {
for (int l = 0; l <= s4; l++) {
if (dp[i][j][k][l] == -1) {
continue;
}
if (i + 1 <= s1 && dp[i][j][k][l] >= byt[1][i].first) {
dp[i + 1][j][k][l] = min(inf, static_cast<long long>(1) * (dp[i][j][k][l] - byt[1][i].first));
}
if (j + 1 <= s2 &&dp[i][j][k][l] >= byt[2][j].first && j + 1 <= s2) {
dp[i][j + 1][k][l] = min(inf, static_cast<long long>(2) * (dp[i][j][k][l] - byt[2][j].first));
}
if (k + 1 <= s3 && dp[i][j][k][l] >= byt[3][k].first && k + 1 <= s3) {
dp[i][j][k + 1][l] = min(inf, static_cast<long long>(3) * (dp[i][j][k][l] - byt[3][k].first));
}
if (l + 1 <= s4 && dp[i][j][k][l] >= byt[4][l].first && l + 1 <= s4) {
dp[i][j][k][l + 1] = min(inf, static_cast<long long>(4) * (dp[i][j][k][l] - byt[4][l].first));
}
}
}
}
}
int mx = 0;
array<int, 4> restore = {0, 0, 0, 0};
for (int i = 0; i <= s1; i++) {
for (int j = 0; j <= s2; j++) {
for (int k = 0; k <= s3; k++) {
for (int l = 0; l <= s4; l++) {
if (dp[i][j][k][l] != -1) {
mx = max(mx, i + j + k + l);
if (mx == i + j + k + l) {
restore = {i, j, k, l};
}
}
}
}
}
}
vector<array<int, 3>> pt;
for (int i = 0; i < restore[0]; i++) {
pt.push_back({1, byt[1][i].first, byt[1][i].second});
}
for (int i = 0; i < restore[1]; i++) {
pt.push_back({2, byt[2][i].first, byt[2][i].second});
}
for (int i = 0; i < restore[2]; i++) {
pt.push_back({3, byt[3][i].first, byt[3][i].second});
}
for (int i = 0; i < restore[3]; i++) {
pt.push_back({4, byt[4][i].first, byt[4][i].second});
}
sort(pt.begin(), pt.end(), [&](array<int, 3> x, array<int, 3> y) {
if (x[0] == 1 && y[0] == 1) {
return (x[0] < y[0]);
}
int p1 = x[1], p2 = y[1], t1 = x[0], t2 = y[0];
return (static_cast<long long>(p1) * static_cast<long long>(t1) * static_cast<long long>(t2 - 1) < static_cast<long long>(p2) * static_cast<long long>(t2) * static_cast<long long>(t1 - 1));
});
vector<int> ans;
for (int i = 0; i < pt.size(); i++) {
ans.push_back(pt[i][2]);
}
return ans;
/*vector<int> pp(5);
while (pp[1] < byt[1].size() || pp[2] < byt[2].size() || pp[3] < byt[3].size() || pp[4] < byt[4].size()) {
vector<int> valid;
for (int i = 1; i <= 4; i++) {
if (pp[i] < byt[i].size() && awa >= byt[i][pp[i]].first) {
valid.push_back(i);
}
}
if (valid.size() == 0) {
break;
}
if (valid.size() == 1) {
awa = static_cast<long long>(valid[0]) * static_cast<long long>(awa - byt[valid[0]][pp[valid[0]]].first);
if (awa > static_cast<long long>(1e15)) {
awa = static_cast<long long>(1e15);
}
order.emplace_back(byt[valid[0]][pp[valid[0]]].second);
++pp[valid[0]];
} else {
pair<int, int> best = make_pair(byt[valid[0]][pp[valid[0]]].first, valid[0]);
int id = 0;
for (int i = 1; i < valid.size(); i++) {
pair<int, int> now = make_pair(byt[valid[i]][pp[valid[i]]].first, valid[i]);
if (static_cast<long long>(now.second) * static_cast<long long>(awa - now.first) > static_cast<long long>(best.second) * static_cast<long long>(awa - best.first)) {
id = i;
best = now;
}
}
awa = static_cast<long long>(valid[id]) * static_cast<long long>(awa - byt[valid[id]][pp[valid[id]]].first);
if (awa > static_cast<long long>(1e15)) {
awa = static_cast<long long>(1e15);
}
order.emplace_back(byt[valid[id]][pp[valid[id]]].second);
++pp[valid[id]];
}
}
return order;*/
}
