#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;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
ll n=P.size();
vector<vector<ll>> pr(P.size());
for (int i=0;i<n;i++)
{
pr[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];
return val1 < val2;
};
sort(pr.begin(), pr.end(),comparator);
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<=30;j++)
{
if(j==0)
{
dp[i][j]={A,-1};
}
else if(i==0)
{
if(j==1 && pr[i][0] <= A)
{
dp[i][j].first=min((A-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};
vector<int> ans;
for (int i=30;i>=0;i--)
{
if(dp[n-1][i]!=bad)
{
ll cur=n-1;
while(i)
{
ans.push_back(pr[dp[cur][i].second].back());
cur=dp[cur][i].second-1;
i--;
}
break;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
