#include "festival.h"
#include <bits/stdc++.h>
#define ll long long
#define inf (ll)1e17
#define dbg(x) cerr<<#x<<' ' << x << endl;
using namespace std;
ll maxans(ll val, vector<vector<ll>>& ones)
{
ll ans=ones.size();
ll sm=0;
for (int i=0;i<ones.size();i++)
{
sm+=ones[i][0];
if(sm>val)
{
return i;
}
}
return ans;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
ll n=P.size();
ll aa=A;
vector<vector<ll>> pr1(P.size());
for (int i=0;i<n;i++)
{
pr1[i]={P[i],T[i],i};
}
auto comparator = [](vector<ll> a, vector<ll> b)
{
ll val1=a[0]*a[1]*b[1]+b[0]*b[1];
ll val2= b[0]*a[1]*b[1] + a[0]*a[1];
if(val1==val2)
{
return a[0] < b[0];
}
return val1 < val2;
};
sort(pr1.begin(), pr1.end(),comparator);
vector<int> ans;
vector<vector<ll>> pr;
for (int i=0;i<n;i++)
{
if((aa-pr1[i][0])*pr1[i][1] >= aa)
{
aa=(aa-pr1[i][0])*pr1[i][1];
aa=min(aa,(ll)1e16);
ans.push_back(pr1[i].back());
}
else
{
pr.push_back(pr1[i]);
}
}
n=pr.size();
vector<vector<ll>> ones;
while(pr.size() && pr.back()[1]==1)
{
ones.push_back(pr.back());
pr.pop_back();
}
reverse(ones.begin(), ones.end());
n=pr.size();
vector<vector<pair<ll,ll>>> dp(n,vector<pair<ll,ll>>(31,{-1,-1}));
for (int i=0;i<n;i++)
{
for (int j=0;j<=dp[i].size()-1;j++)
{
if(j==0)
{
dp[i][j]={aa,-1};
}
else if(i==0)
{
if(j==1 && pr[i][0] <= aa)
{
dp[i][j].first=min((aa-pr[i][0])*pr[i][1],(ll)1e16);
dp[i][j].second=i;
}
}
else
{
dp[i][j]=dp[i-1][j];
if(pr[i][0]<=dp[i-1][j-1].first)
{
ll val=min((ll)1e16,(dp[i-1][j-1].first-pr[i][0])*pr[i][1]);
if(val > dp[i][j].first)
{
dp[i][j]={val,i};
}
}
}
}
}
pair<ll,ll> bad={-1,-1};
ll bestans=0;
if(n!=0)
{for (int i=dp[0].size()-1;i>=0;i--)
{
if(dp[n-1][i]!=bad)
{
bestans=max(bestans,i+maxans(dp[n-1][i].first,ones));
}
}}
ll index=maxans(aa,ones);
if(index >= bestans)
{
for (int i=0;i<index;i++)
{
ans.push_back(ones[i].back());
}
}
else
{
ll val=0;
vector<ll> ans2;
for (int i=dp[0].size()-1;i>=0;i--)
{
ll val1=maxans(dp[n-1][i].first,ones);
if(dp[n-1][i]!=bad && val1+i==bestans)
{
val=val1;
ll cur=n-1;
while(i)
{
ans2.push_back(pr[dp[cur][i].second].back());
cur=dp[cur][i].second-1;
i--;
}
break;
}
}
for (int i=ans2.size()-1;i>=0;i--)
{
ans.push_back(ans2[i]);
}
for (int j=0;j<val;j++)
{
ans.push_back(ones[j].back());
}
}
return ans;
}
