#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const ll INF=1e16;
vector<int> max_coupons(int A1,vector<int>P1,vector<int>T1){
ll A=A1;vector<ll>P,T;
int n=P1.size(),ord[n]={0};
for(int i=0;i<n;i++)P.pb(P1[i]),T.pb(T1[i]);
iota(ord,ord+n,0);
sort(ord,ord+n,[&](int i,int j){
if(T[i]==1&&T[j]==1)return P[i]<P[j];
if(T[i]==1)return false;
if(T[j]==1)return true;
return P[i]*T[i]*(T[j]-1)<P[j]*T[j]*(T[i]-1);
});
vector<int>res,a[5];
for(auto i:ord){
if((A-P[i])*T[i]>=A){
A=min((A-P[i])*T[i],INF);
res.pb(i);
}
else a[T[i]].pb(i);
}
for(int j=2;j<=4;j++){
ll X=A;
for(int I=0;I<(int)a[j].size();I++){
int i=a[j][I];
if((X-P[i])*T[i]<0){
a[j].resize(I);
break;
}
X=(X-P[i])*T[i];
}
}
int invord[n];
for(int i=0;i<n;i++)invord[ord[i]]=i;
vector<int>ans;
for(int I=0;I<=(int)a[2].size();I++){
for(int J=0;J<=(int)a[3].size();J++){
for(int K=0;K<=(int)a[4].size();K++){
vector<int>ids;
for(int i=0;i<I;i++)ids.pb(a[2][i]);
for(int i=0;i<J;i++)ids.pb(a[3][i]);
for(int i=0;i<K;i++)ids.pb(a[4][i]);
sort(ids.begin(),ids.end(),[&](int i,int j){return invord[i]<invord[j];});
ll X=A;
bool moze=true;
for(auto i:ids){
if((X-P[i])*T[i]<0){moze=false;break;}
X=(X-P[i])*T[i];
}
if(moze){
for(auto i:a[1]){
if((X-P[i])*T[i]<0)break;
X=(X-P[i])*T[i];
ids.pb(i);
}
if(ids.size()>ans.size())ans=ids;
}
}
}
}
for(auto i:ans)res.pb(i);
return res;
}
