#include "festival.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define ff first
#define ss second
bool com(pii a,pii b)
{
if (a.ss==b.ss)
return a.ff<=b.ff;
return (a.ff*a.ss*(b.ss-1))<=(b.ff*b.ss*(a.ss-1));
}
vector<int> max_coupons(int a, vector<int> P, vector<int> T)
{
map<pair<int,int>,vector<int>>inds;
int n=P.size();
ll A=a;
vector<pii>vals;
for (int i=0;i<n;i++)
{
inds[{P[i],T[i]}].push_back(i);
vals.push_back({P[i],T[i]});
}
sort(begin(vals),end(vals),com);
reverse(begin(vals),end(vals));
vector<pii>tk;
while (vals.size())
{
pii z=vals.back();
if ((A-z.ff)*z.ss>=A)
{
tk.push_back(z);
A=(A-z.ff)*z.ss;
A=min(A,(ll)1e18);
vals.pop_back();
continue;
}
break;
}
vector<ll>pr[5]={};
while (vals.size())
{
pr[vals.back().ss].push_back(vals.back().ff);
vals.pop_back();
}
for (int i=2;i<=4;i++)
{
ll cur=A;
vector<ll>vld;
sort(begin(pr[i]),end(pr[i]));
for (auto j:pr[i])
{
if (j>cur)
break;
cur=(cur-j)*i;
vld.push_back(j);
}
pr[i]=vld;
}
int s2=pr[2].size(),s3=pr[3].size(),s4=pr[4].size();
ll dp[s2+10][s3+10][s4+10]={};
for (int i=0;i<=s2;i++)
for (int j=0;j<=s3;j++)
for (int k=0;k<=s4;k++)
dp[i][j][k]=-1;
vector<ll>pre={0};
for (auto i:pr[1])
pre.push_back(pre.back()+i);
dp[0][0][0]=A;
int mx=0;
vector<int>ind={0,0,0};
for (int i=0;i<=s2;i++)
for (int j=0;j<=s3;j++)
for (int k=0;k<=s4;k++)
{
if (i>0)
{
if (pr[2][i-1]<=dp[i-1][j][k])
dp[i][j][k]=max(dp[i][j][k],(dp[i-1][j][k]-pr[2][i-1])*2ll);
}
if (j>0)
{
if (pr[3][j-1]<=dp[i][j-1][k])
dp[i][j][k]=max(dp[i][j][k],(dp[i][j-1][k]-pr[3][j-1])*3ll);
}
if (k>0)
{
if (pr[4][k-1]<=dp[i][j][k-1])
dp[i][j][k]=max(dp[i][j][k],(dp[i][j][k-1]-pr[4][k-1])*4ll);
}
if (dp[i][j][k]>=0)
{
ll z=upper_bound(begin(pre),end(pre),dp[i][j][k])-begin(pre);
if (i+j+k+z-1>mx)
{
mx=i+j+k+z-1;
ind={i,j,k};
}
}
}
int i=ind[0],j=ind[1],k=ind[2];
int rem=mx-i-j-k;
vector<pii>tl;
while (max(i,max(j,k))>0)
{
if (i>0&&dp[i][j][k]==(dp[i-1][j][k]-pr[2][i-1])*2ll)
{
tl.push_back({pr[2][i-1],2});
i--;
}
if (j>0&&dp[i][j][k]==(dp[i][j-1][k]-pr[3][j-1])*3ll)
{
tl.push_back({pr[3][j-1],3});
j--;
}
if (k>0&&dp[i][j][k]==(dp[i][j][k-1]-pr[4][k-1])*4ll)
{
tl.push_back({pr[4][k-1],4});
k--;
}
}
reverse(begin(tl),end(tl));
for (int l=0;l<rem;l++)
tl.push_back({pr[1][l],1});
for (auto i:tl)
tk.push_back(i);
vector<int>ans;
for (auto i:tk)
{
ans.push_back(inds[i].back());
inds[i].pop_back();
}
return ans;
}
