Given N products and M customers, for each customer find the list of distinct products they can buy without exceeding their budget such that the number of products purchased is maximized. If multiple solutions yield the same maximum count: (1) choose the set with the smallest total spend; (2) if still tied, choose the lexicographically smallest list of product_ids. You may use each product at most once per customer; assume infinite stock across customers (each customer considers the full catalog independently). Return, for each customer, (customer_id, max_count, chosen_product_ids in ascending order by price then product_id). Design an algorithm with preprocessing O(N log N) and query time O(log N) per customer (excluding output size), and implement it. Justify correctness.
Input format
Constraints
Required approach
Example products = [(1,100),(2,100),(3,300),(4,500)] customers = [("A",500)] Output: ("A", 3, [1,2,3]) because taking the three cheapest maximizes count; total spend 500.
Edge cases to handle
Deliverables