#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll AMAX = 5e15; //if exceeds this -> can buy everything
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
ll Ac = A;
vector<pii> vcp[5]; //T -> {P,idx}
ll N = P.size();
for (ll i=0;i<N;i++) {
vcp[T[i]].push_back({P[i],i});
}
for (ll t=1;t<=4;t++) {
sort(vcp[t].begin(),vcp[t].end());
}
queue<pii> qcp[5];
for (ll t=1;t<=4;t++) {
for (pii p0: vcp[t]) {
qcp[t].push(p0);
}
}
map<ll,ll> m1c; //count how many 1s from total amount available
m1c[0]=0;
ll tnum = 0; ll tval = 0;
for (pii p0: vcp[1]) {
tnum++; tval+=p0.first;
m1c[tval]=tnum;
}
//first step: all steps that do not decrease Ac
vector<int> R; //guaranteed R
while(1) { //Ac = current A
if (Ac>=AMAX) { //guaranteed can buy everything LOL
for (ll t=1;t<=4;t++) {
while (!qcp[t].empty()) {
pii p0 = qcp[t].front(); qcp[t].pop();
R.push_back(p0.second);
}
}
return R; //terminated here!
}
ll xc = 6*Ac+1; ll tc = -1;
for (ll t=2;t<=4;t++) {
if (!qcp[t].empty()) {
ll xn = (6*t*(qcp[t].front().first))/(t-1);
if (xn<xc) {
xc = xn; tc = t;
}
}
}
if (tc==-1) {
break;
} else {
pii p0 = qcp[tc].front(); qcp[tc].pop();
R.push_back(p0.second);
assert((tc*(Ac-p0.first))>=Ac);
Ac = tc*(Ac-p0.first);
}
}
// cout << "initial R: \n";
// for (ll x: R) {
// cout << "x="<<x<<"\n";
// }
//now all must be decreasing: at most 60 decrements total
vector<pii> vcp2[5]; //everything that's left
for (ll t=1;t<=4;t++) {
while (!qcp[t].empty()) {
vcp2[t].push_back(qcp[t].front()); qcp[t].pop();
}
}
ll mnc = -1; //maximum number of numbers in this last step
array<ll,3> cnstr = {-1,-1,-1};
for (ll n2=0;n2<=(min((ll)vcp2[2].size(),60LL));n2++) {
for (ll n3=0;n3<=(min((ll)vcp2[3].size(),60LL));n3++) {
for (ll n4=0;n4<=(min((ll)vcp2[4].size(),60LL));n4++) {
vector<array<ll,3>> ti0; //{xc,T,P}
ll Af = Ac;
for (ll n=0;n<n2;n++) {
ti0.push_back({(12*vcp2[2][n].first),2,vcp2[2][n].first});
}
for (ll n=0;n<n3;n++) {
ti0.push_back({9*vcp2[3][n].first,3,vcp2[3][n].first});
}
for (ll n=0;n<n4;n++) {
ti0.push_back({8*vcp2[4][n].first,4,vcp2[4][n].first});
}
sort(ti0.begin(),ti0.end());
bool bf = 0; //bool fail
for (auto A0: ti0) {
Af = A0[1]*(Af-A0[2]);
if (Af<0) {
bf = 1; break;
}
}
if (bf==1) {
break; //should be faster than continue NGL: can prob eliminate
}
auto A0 = --m1c.upper_bound(Af);
ll nctr = (*A0).second+n2+n3+n4;
if (mnc<nctr) {
mnc = nctr;
cnstr = {n2,n3,n4};
}
}
}
}
assert(mnc>=0);
ll n2 = cnstr[0]; ll n3 = cnstr[1]; ll n4 = cnstr[2];
vector<array<ll,4>> qi0; //{xc,T,P,idx}
ll Af = Ac;
for (ll n=0;n<n2;n++) {
qi0.push_back({12*vcp2[2][n].first,2,vcp2[2][n].first,vcp2[2][n].second});
}
for (ll n=0;n<n3;n++) {
qi0.push_back({9*vcp2[3][n].first,3,vcp2[3][n].first,vcp2[3][n].second});
}
for (ll n=0;n<n4;n++) {
qi0.push_back({8*vcp2[4][n].first,4,vcp2[4][n].first,vcp2[4][n].second});
}
sort(qi0.begin(),qi0.end());
for (auto A0: qi0) {
Af = A0[1]*(Af-A0[2]);
R.push_back(A0[3]);
assert(Af>=0);
}
for (ll T=0;T<((ll)vcp2[1].size());T++) {
if (Af>=vcp2[1][T].first) {
Af -= vcp2[1][T].first;
R.push_back(vcp2[1][T].second);
}
}
return R;
}
