#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]));
vector<pair<int,int>> srt;
for (int i = 0; i < 4; i++) { for (int j = 0; j < sz(v[i]); j++) srt.push_back({i+1,j}); }
sort(all(srt), [](pair<int,int> a, pair<int,int> b){
/*cerr << v[a.first][a.second].first*a.first*b.first+b.first*v[b.first][b.second].first << " ";
cerr << v[b.first][b.second].first*a.first*b.first+a.first*v[a.first][a.second].first << " ";
cerr << "\n";*/
return v[a.first-1][a.second].first*a.first*b.first+b.first*v[b.first-1][b.second].first<v[b.first-1][b.second].first*a.first*b.first+a.first*v[a.first-1][a.second].first;
});
int cv[4]={0,0,0,0};
vector<signed> outp;
int a=A;
int lst1=-1;
int lstv=a;
for (int i = 0; i < sz(srt); i++)
{
srt[i].first--;
int mxI=srt[i].first;
if((a-v[mxI][cv[mxI]].first)*(mxI+1)<a) break;
lstv=a;
a=(a-v[mxI][cv[mxI]].first)*(mxI+1);
a=min(MAX_VAL,a);
outp.push_back(v[mxI][cv[mxI]].second);
cv[mxI]++;
lst1=mxI;
}
/*if(lst1!=-1) cv[lst1]--;
a=lstv;*/
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;
}
