#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]));
int cv[4]={0,0,0,0};
vector<signed> outp;
int a=A;
for (int i = 0; i < n; i++)
{
int mx=-1;
int mxI=-1;
for (int j = 0; j < 4; j++)
{
if(cv[j]>=sz(v[j])) continue;
cv[j]++;
int mx2=0;
for (int k = 0; k < 4; k++)
{
if(cv[k]==sz(v[k])) continue;
mx2=max(v[k].back().first,mx2);
}
cv[j]--;
if((a-v[j][cv[j]].first)*(j+1)>mx&&mx2<=(a-v[j][cv[j]].first)*(j+1)){
mx=(a-v[j][cv[j]].first)*(j+1);
mxI=j;
}
}
if(mxI==-1) break;
a=min(MAX_VAL,mx);
outp.push_back(v[mxI][cv[mxI]].second);
cv[mxI]++;
}
return outp;
}
