#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 2e17;
const int MN = 74;
ll dp[MN][MN][MN][MN];
int pp[MN][MN][MN][MN];
int n;
ll tot;
void dbg(int x) {
cout << "DEBUG: " << x << "\n";
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
n = P.size();
tot = A;
vector<vector<pair<ll, int>>> els(5);
for (int i = 1; i <= 4; i++) els[i].push_back({-1, -1});
for (int i = 0; i < n; i++) {
els[T[i]].push_back({P[i], i});
}
for (int i = 1; i <= 4; i++) sort(els[i].begin(), els[i].end());
int a = els[1].size() - 1, b = els[2].size() - 1, c = els[3].size() - 1, d = els[4].size() - 1;
dp[0][0][0][0] = tot;
vector<int> cons = {0, 0, 0, 0};
int best = 0;
for (int i = 0; i <= a; i++) {
for (int j = 0; j <= b; j++) {
for (int k = 0; k <= c; k++) {
for (int l = 0; l <= d; l++) {
if (best == a + b + c + d) break;
if (i == 0 && j == 0 && k == 0 && l == 0) continue;
dp[i][j][k][l] = -1;
if (i > 0) {
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l] - els[1][i].first);
pp[i][j][k][l] = 1;
}
if (j > 0) {
int v = 2 * dp[i][j-1][k][l] - 2 * els[2][j].first;
if (v >= dp[i][j][k][l]) {
pp[i][j][k][l] = 2;
dp[i][j][k][l] = v;
}
}
if (k > 0) {
int v = 3 * dp[i][j][k-1][l] - 3 * els[3][k].first;
if (v >= dp[i][j][k][l]) {
pp[i][j][k][l] = 3;
dp[i][j][k][l] = v;
}
}
if (l > 0) {
int v = 4 * dp[i][j][k][l-1] - 4 * els[4][l].first;
if (v >= dp[i][j][k][l]) {
pp[i][j][k][l] = 4;
dp[i][j][k][l] = v;
}
}
if (dp[i][j][k][l] > INF) {
cons = {a, b, c, d};
best = a + b + c + d;
break;
}
if (dp[i][j][k][l] >= 0) {
if (i + j + k + l >= best) {
cons = {i, j, k, l};
best = i + j + k + l;
}
}
}
}
}
}
//dbg(dp[0][0][0][0]);
//dbg(tot);
vector<int> ans;
while (cons[0] + cons[1] + cons[2] + cons[3] > 0) {
int i = cons[0];
int j = cons[1];
int k = cons[2];
int l = cons[3];
if (pp[i][j][k][l] == 1) {
ans.push_back(els[1][i].second);
cons[0]--;
}
else if (pp[i][j][k][l] == 2) {
ans.push_back(els[2][j].second);
cons[1]--;
}
else if (pp[i][j][k][l] == 3) {
ans.push_back(els[3][k].second);
cons[2]--;
}
else if (pp[i][j][k][l] == 4) {
ans.push_back(els[4][l].second);
cons[3]--;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
