#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
int n = p.size();
vector<array<int, 3>> pt(n);
for (int i = 0; i < n; i++) {
pt[i] = {p[i], t[i], i};
}
vector<vector<pair<int, int>>> byt(5);
for (int i = 0; i < n; i++) {
byt[pt[i][1]].emplace_back(pt[i][0], i);
}
for (int i = 1; i <= 4; i++) {
sort(byt[i].begin(), byt[i].end());
}
vector<int> order;
long long awa = a;
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.first) * static_cast<long long>(now.second) * static_cast<long long>(best.second - 1) < static_cast<long long>(best.first) * static_cast<long long>(best.second) * static_cast<long long>(now.second - 1)) {
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;
}
