#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;
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]));
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];
}
cerr << sz(v[0]);
map<pair<pair<int,int>,int>,int> dp;
map<pair<pair<int,int>,int>,pair<int,int>> last;
dp[{{0,0},0}]=A+1;
int mx=upper_bound(all(pref), A)-pref.begin();
int mxI[3]={0,0,0};
queue<pair<pair<int,int>,int>> q;
q.push({{0,0},0});
while(!q.empty()){
int k=q.front().first.first;
int v1=q.front().first.second;
int v2=q.front().second;
int v3=k-v1-v2;
q.pop();
int a=min(MAX_VAL,dp[{{k,v1},v2}]-1);
int up=upper_bound(all(pref),A)-pref.begin();
if(up+k>mx){
mx=up+k;
mxI[0]=k;
mxI[1]=v1;
mxI[2]=v2;
}
if(v1<sz(v[1])&&v[1][v1].first<a){
int nv=(a-v[1][v1].first)*2;
if(dp[{{k+1,v1+1},v2}]==0) q.push({{k+1,v1+1},v2});
if(dp[{{k+1,v1+1},v2}]<nv+1){
last[{{k+1,v1+1},v2}]={1,v[1][v1].second};
}
}
if(v2<sz(v[2])&&v[2][v2].first<a){
int nv=(a-v[2][v2].first)*3;
if(dp[{{k+1,v1},v2+1}]==0) q.push({{k+1,v1},v2+1});
if(dp[{{k+1,v1},v2+1}]<nv+1){
last[{{k+1,v1},v2+1}]={2,v[2][v2].second};
dp[{{k+1,v1},v2+1}]=nv+1;
}
}
if(v3<sz(v[3])&&v[3][v3].first<a){
int nv=(a-v[3][v3].first)*4;
if(dp[{{k+1,v1},v2}]==0) q.push({{k+1,v1},v2});
if(dp[{{k+1,v1},v2}]<nv+1){
last[{{k+1,v1},v2}]={3,v[3][v3].second};
dp[{{k+1,v1},v2}]=nv+1;
}
}
}
vector<signed> outp;
int a=dp[{{mxI[0],mxI[1]},mxI[2]}]-1;
while(mxI[0]>0){
outp.push_back(last[{{mxI[0],mxI[1]},mxI[2]}].second);
if(last[{{mxI[0],mxI[1]},mxI[2]}].first<3) mxI[last[{{mxI[0],mxI[1]},mxI[2]}].first]--;
mxI[0]--;
}
reverse(all(outp));
int v0=0;
while(v0<sz(v[0])&&a>=v[0][v0].first){
a-=v[0][v0].first;
outp.push_back(v[0][v0].second);
v0++;
}
return {outp};
}
