#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=1e16;
std::vector<signed> max_coupons(signed _A, std::vector<signed> P, std::vector<signed> T) {
v.resize(4);
n=sz(P);
int A=_A;
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=a-1;
int mxI=-1;
for (int j = 3; j >= 1; j--)
{
if(cv[j]>=sz(v[j])) continue;
if((a-v[j][cv[j]].first)*(j+1)>mx){
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]++;
}
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];
}
map<pair<pair<int,int>,int>,int> dp;
map<pair<pair<int,int>,int>,pair<int,int>> last;
A=a;
int mxI[3]={cv[1]+cv[2]+cv[3],cv[1],cv[2]};
int bk=mxI[0];
dp[{{mxI[0],mxI[1]},mxI[2]}]=A+1;
int mx=upper_bound(all(pref), A)-pref.begin();
queue<pair<pair<int,int>,int>> q;
q.push({{mxI[0],mxI[1]},mxI[2]});
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();
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};
dp[{{k+1,v1+1},v2}]=nv+1;
}
}
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;
a=dp[{{mxI[0],mxI[1]},mxI[2]}]-1;
while(mxI[0]>bk){
_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));
for (auto u : _outp) outp.push_back(u);
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;
}
