#include "festival.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll,ll>
const ll mxN = 1e6 + 5;
using namespace std;
vector<pii>t[5];
bool vis[mxN];
ll prfx[mxN];
ll calc(ll a,pii p,ll t){
return (a - p.F) * t;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
ll a = A;
ll n = P.size();
for(ll i = 0 ;i < P.size();i++){
t[T[i]].push_back({P[i],i});
}
ll ans = 0;
vector<int>sol = {};
for(ll i = 1;i <= 4;i++) sort(t[i].begin(),t[i].end());
for(ll i = 0;i < t[1].size();i++){
prfx[i] = t[1][i].F;
if(i) prfx[i] += prfx[i - 1];
}
ll oga = a;
for(ll i = 0;i <= t[2].size();i++){
// for(ll j = 0;j <= t[3].size();j++){
// for(ll k = 0;k <= t[4].size();k++){
// }
// }
a = oga;
ll num = 0;
vector<int>vec = {};
for(ll el = 0; el < i;el++){
if(calc(a,t[2][el],2) < 0) continue;
if(a < 1e17) a = calc(a,t[2][el],2);
num++;
vec.push_back(t[2][el].S);
}
for(ll el = 0;el < t[1].size();el++){
if(a >= t[1][el].F){
num++;
a -= t[1][el].F;
vec.push_back(t[1][el].S);
}
}
if(a >= 0){
if(num > ans){
ans = num;
sol = vec;
}
}
}
return sol;
}
