#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
std::vector <int> max_coupons(int A, std::vector <int> P, std::vector <int> T) {
std::vector <int> ret;
std::vector <std::vector <std::pair <int, int>>> save(5);
for (int i = 0; i < (int) T.size(); i++) {
save[T[i]].push_back(std::make_pair(P[i], i));
}
for (int i = 1; i <= 4; i++) {
std::sort(save[i].begin(), save[i].end());
std::reverse(save[i].begin(), save[i].end());
}
long long X = A;
while (true) {
bool checkEmpty = true;
for (int i = 1; i <= 4; i++) {
if (save[i].empty() == false) {
checkEmpty = false;
}
}
if (checkEmpty == true) {
break;
}
long long maxi = -1;
int type = -1;
int id = -1;
for (int i = 1; i <= 4; i++) {
if (save[i].empty() == true) {
continue;
}
std::pair <int, int> element = save[i].back();
if (X >= element.first) {
if (maxi < (X - element.first) * i) {
maxi = (X - element.first) * i;
type = i;
id = element.second;
}
}
}
if (type == -1) {
break;
}
save[type].pop_back();
ret.push_back(id);
X = maxi;
}
return ret;
}
