Shopping at Ozone Galleria Mall

You are visiting the Ozone Galleria Mall which has a row of n shops arranged left-to-right. Each shop sells exactly one product whose price is given by the array prices[], where prices[i] is the cost of the product at shop i. All prices are positive integers and the array is sorted in non-decreasing order. You start at shop pos (1-based index) and have amount dollars in your wallet. From your starting shop you can only move rightward, buying any subset of the products you encounter, but you must buy them in increasing order of their indices (i.e., you cannot skip a cheaper product and come back later). Your goal is to maximize the number of distinct products you can buy without exceeding your budget. For each of q independent queries, each specified by (pos, amount), output the maximum number of products you can purchase.