#include "festival.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<vector<vector<vector<int>>>> dp;
vector<vector<vector<vector<pair<int,int>>>>> prv;
int n;
vector<vector<pair<int,int>>> v(4);
const int MAX_VAL=1e15;
std::vector<signed> max_coupons(signed A, std::vector<signed> P, std::vector<signed> T) {
v.resize(4);
n=sz(P);
for (int i = 0; i < n; i++) v[T[i]-1].push_back({P[i],i});
for (int i = 0; i < 4; i++) sort(all(v[i]));
vector<int> pref(sz(v[0]));
for (int i = 0; i < sz(v[0]); i++)
{
pref[i]=v[0][i].first;
if(i>0) pref[i]+=pref[i-1];
}
int mxI=0;
int mx=0;
int a=A;
for (int i = 0; i <= sz(v[1]); i++)
{
if(a<0) break;
int up=upper_bound(all(pref), a)-pref.begin();
if(i+up>mx){
mx=i+up;
mxI=i;
}
if(i<sz(v[1])) a=min(MAX_VAL,(a-v[1][i].first)*2);
}
a=A;
vector<signed> outp;
for (int i = 0; i < mxI; i++)
{
outp.push_back(v[1][i].second);
a=min(MAX_VAL,(a-v[1][i].first)*2);
}
for (int i = 0; i < sz(v[0]); i++)
{
if(a<v[0][i].first) break;
outp.push_back(v[0][i].second);
a-=v[0][i].first;
}
return outp;
}
