#include <iostream>
#include <algorithm>
using namespace std;
struct dp_state{
int multiplier_ones, multiplier_twos, multiplier_threes, multiplier_fours;
};
vector<pair<int, int>> coupons_type[5];
int from_where[71][71][71][71];
long long dp[71][71][71][71];
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T){
for (int i = 0;i < P.size();i++){
coupons_type[T[i]].push_back({P[i], i});
}
for (int j = 1;j <= 4;j++){
sort(coupons_type[j].begin(), coupons_type[j].end());
}
for (int i = 0;i <= coupons_type[1].size();i++){
for (int j = 0;j <= coupons_type[2].size();j++){
for (int k = 0;k <= coupons_type[3].size();k++){
for (int l = 0;l <= coupons_type[4].size();l++){
dp[i][j][k][l] = -1;
}
}
}
}
dp[0][0][0][0] = A;
for (int i = 0;i <= coupons_type[1].size();i++){
for (int j = 0;j <= coupons_type[2].size();j++){
for (int k = 0;k <= coupons_type[3].size();k++){
for (int l = 0;l <= coupons_type[4].size();l++){
if (i >= 1 and dp[i - 1][j][k][l] >= coupons_type[1][i - 1].first){
if (dp[i][j][k][l] < (dp[i - 1][j][k][l] - coupons_type[1][i - 1].first) * 1){
dp[i][j][k][l] = (dp[i - 1][j][k][l] - coupons_type[1][i - 1].first) * 1;
from_where[i][j][k][l] = 1;
}
}
if (j >= 1 and dp[i][j - 1][k][l] >= coupons_type[2][j - 1].first){
if (dp[i][j][k][l] < (dp[i][j - 1][k][l] - coupons_type[2][j - 1].first) * 2){
dp[i][j][k][l] = (dp[i][j - 1][k][l] - coupons_type[2][j - 1].first) * 2;
from_where[i][j][k][l] = 2;
}
}
if (k >= 1 and dp[i][j][k - 1][l] >= coupons_type[3][k - 1].first){
if (dp[i][j][k][l] < (dp[i][j][k - 1][l] - coupons_type[3][k - 1].first) * 3){
dp[i][j][k][l] = (dp[i][j][k - 1][l] - coupons_type[3][k - 1].first) * 3;
from_where[i][j][k][l] = 3;
}
}
if (l >= 1 and dp[i][j][k][l - 1] >= coupons_type[4][l - 1].first){
if (dp[i][j][k][l] < (dp[i][j][k][l - 1] - coupons_type[4][l - 1].first) * 4){
dp[i][j][k][l] = (dp[i][j][k][l - 1] - coupons_type[4][l - 1].first) * 4;
from_where[i][j][k][l] = 4;
}
}
dp[i][j][k][l] = min(dp[i][j][k][l], 1000000000000000LL);
}
}
}
}
dp_state best_state = {0, 0, 0, 0};
for (int i = 0;i <= coupons_type[1].size();i++){
for (int j = 0;j <= coupons_type[2].size();j++){
for (int k = 0;k <= coupons_type[3].size();k++){
for (int l = 0;l <= coupons_type[4].size();l++){
if (dp[i][j][k][l] != -1){
if ((i + j + k + l) > (best_state.multiplier_ones + best_state.multiplier_twos + best_state.multiplier_threes + best_state.multiplier_fours)){
best_state = {i, j, k, l};
}
}
}
}
}
}
vector<int> operations;
while (best_state.multiplier_ones != 0 or best_state.multiplier_twos != 0 or best_state.multiplier_threes != 0 or best_state.multiplier_fours != 0){
int value = from_where[best_state.multiplier_ones][best_state.multiplier_twos][best_state.multiplier_threes][best_state.multiplier_fours];
if (value == 1){
operations.push_back(coupons_type[1][best_state.multiplier_ones - 1].second);
best_state.multiplier_ones--;
}
else if (value == 2){
operations.push_back(coupons_type[2][best_state.multiplier_twos - 1].second);
best_state.multiplier_twos--;
}
else if (value == 3){
operations.push_back(coupons_type[3][best_state.multiplier_threes - 1].second);
best_state.multiplier_threes--;
}
else{
operations.push_back(coupons_type[4][best_state.multiplier_fours - 1].second);
best_state.multiplier_fours--;
}
}
reverse(operations.begin(), operations.end());
return operations;
}
