#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int N = P.size();
vector<vector<int>> coupons(4);
for(int i=0; i<N; i++) {
coupons[T[i] - 1].push_back(i);
}
for(int i=0; i<4; i++) sort(coupons[i].begin(), coupons[i].end(), [&](int a, int b) {
return P[a] < P[b];
});
vector<int> ids(4);
vector<int> bought;
long long money = A;
long long sum = accumulate(P.begin(), P.end(), 0ll);
while(1) {
int best = -1;
long long score = 0;
for(int i=0; i<4; i++) {
if(ids[i] >= coupons[i].size() or P[coupons[i][ids[i]]] > money) continue;
long long p = P[coupons[i][ids[i]]];
long long t = i + 1;
cerr << (money - p) * t << endl;
if((money - p) * t >= score) {
score = (money - p) * t;
best = i;
}
}
cerr << best << endl;
if(best == -1) break;
money = score;
if(money > sum) break;
bought.push_back(coupons[best][ids[best]]);
ids[best]++;
}
if(money > sum) {
for(int i=0; i<4; i++) {
for(int j = ids[i]; j<coupons[i].size(); j++) {
bought.push_back(coupons[i][j]);
}
}
}
return bought;
}
