#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=1e11;
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]));
dp.resize(n+1, vector<vector<vector<int>>>(sz(v[0])+1, vector<vector<int>>(sz(v[1])+1, vector<int>(sz(v[2])+1,-1))));
prv.resize(n+1, vector<vector<vector<pair<int,int>>>>(sz(v[0])+1, vector<vector<pair<int,int>>>(sz(v[1])+1, vector<pair<int,int>>(sz(v[2])+1,{-1,-1}))));
dp[0][0][0][0]=A;
int mx=0;
int mxI[4]={0,0,0,0};
for (int k = 0; k <= n; k++)
{
for (int v0 = 0; v0 <= min(k,sz(v[0])); v0++)
{
for (int v1 = 0; v1 <= min(k-v0,sz(v[1])); v1++)
{
for (int v2 = 0; v2 <= min(k-v0-v1,sz(v[2])); v2++)
{
int v3=k-v0-v1-v2;
if(v3>sz(v[3])) continue;
int a=min(MAX_VAL,dp[k][v0][v1][v2]);
if(a==-1) continue;
if(k>mx){
mxI[0]=k;
mxI[1]=v0;
mxI[2]=v1;
mxI[3]=v2;
mx=k;
}
mx=max(k,mx);
if(mx==n) break;
if(v0<sz(v[0])&&v[0][v0].first<=a){
if(dp[k+1][v0+1][v1][v2]<a-v[0][v0].first){
dp[k+1][v0+1][v1][v2]=a-v[0][v0].first;
prv[k+1][v0+1][v1][v2]={0,v[0][v0].second};
}
}
if(v1<sz(v[1])&&v[1][v1].first<=a){
if(dp[k+1][v0][v1+1][v2]<(a-v[1][v1].first)*2){
dp[k+1][v0][v1+1][v2]=(a-v[1][v1].first)*2;
prv[k+1][v0][v1+1][v2]={1,v[1][v1].second};
}
}
if(v2<sz(v[2])&&v[2][v2].first<=a){
if(dp[k+1][v0][v1][v2+1]<(a-v[2][v2].first)*3){
dp[k+1][v0][v1][v2+1]=(a-v[2][v2].first)*3;
prv[k+1][v0][v1][v2+1]={2,v[2][v2].second};
}
}
if(v3<sz(v[3])&&v[3][v3].first<=a){
if(dp[k+1][v0][v1][v2]<(a-v[3][v3].first)*4){
dp[k+1][v0][v1][v2]=(a-v[3][v3].first)*4;
prv[k+1][v0][v1][v2]={3,v[3][v3].second};
}
}
}
}
}
}
vector<signed> outp;
while(mxI[0]>0){
outp.push_back(prv[mxI[0]][mxI[1]][mxI[2]][mxI[3]].second);
if(prv[mxI[0]][mxI[1]][mxI[2]][mxI[3]].first<3) mxI[prv[mxI[0]][mxI[1]][mxI[2]][mxI[3]].first+1]--;
mxI[0]--;
}
reverse(all(outp));
return {outp};
}
