Purchase Optimization

Alex is shopping at Ozone Galleria Mall, where cubicles sell products at fixed prices. The cubicles are arranged so that prices is in non-decreasing order. You are given:

• prices, where prices[i] is the price at the (i + 1)th cubicle
• pos, where pos[i] is Alex's starting cubicle for the ith query (1-indexed)
• amount, where amount[i] is Alex's budget for the ith query For each query, Alex visits cubicles from pos[i] through n moving only to the right. Alex may buy at most one product from each visited cubicle, and the total cost must not exceed amount[i]. Return an array where the ith value is the maximum number of products Alex can buy for the ith query.

For the three queries, Alex can buy at most 2 products from cubicle 2 onward, all 5 products from cubicle 1 onward, and 0 products from cubicle 5 onward.

The cheapest valid suffix purchases are [2], [2,2,3], and [3,6] respectively.