#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
vector<int> max_coupons(int A, vector<int> P, vector<int> T){
ll cost = A, n = P.size();
vector<int> ans,use(n, 0);
vector<pair<ll,int>> mp[5];
for(int i = 0; i < n; i++){
mp[T[i]].push_back({P[i],i});
}
for(int i = 1; i <= 4; i++) sort(mp[i].begin(), mp[i].end());
struct item{
int t, idx;
ll p;
};
struct cmp{
bool operator()(item const &a, item const &b){
if(a.t != b.t) return a.t < b.t;
return a.p > b.p;
}
};
priority_queue<item, vector<item>, cmp> pq;
int pr2 = 0, pr3 = 0, pr4 = 0;
int sz2 = mp[2].size(), sz3 = mp[3].size(), sz4 = mp[4].size();
auto hitung = [&](int t, int &pt, int sz){
while(pt < sz && mp[t][pt].fi <= cost){
pq.push({t, mp[t][pt].se, mp[t][pt].fi});
pt++;
}
};
hitung(4, pr4, sz4);
hitung(3, pr3, sz3);
hitung(2, pr2, sz2);
while(!pq.empty()){
auto it = pq.top(); pq.pop();
if(use[it.idx]) continue;
use[it.idx] = 1;
cost = (cost-it.p)*it.t;
ans.push_back(it.idx);
hitung(4, pr4, sz4);
hitung(3, pr3, sz3);
hitung(2, pr2, sz2);
}
for(auto &pr : mp[1]){
if(pr.fi <= cost){
cost = (cost-pr.fi);
ans.push_back(pr.se);
}else break;
}
return ans;
}
