Maximize products bought under budget

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 - products: list of (product_id INT, price INT) with price >= 0 - customers: list of (customer_id INT, budget INT) with budget >= 0 Constraints - 1 ≤ N, M ≤ 200,000; 0 ≤ price, budget ≤ 1e9 - Ties on price are broken by smaller product_id Required approach - Pre-sort products by (price ASC, product_id ASC) and build prefix sums of prices and parallel array of product_ids. - For each budget B, find k = max index such that prefix_sum[k] ≤ B via binary search; output the first k product_ids in that sorted order. 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 - Budget < cheapest price → empty list. - Budget ≥ sum of all prices → all product_ids. - Many equal prices: verify lexicographic tie-break by product_id. Deliverables - Working implementation (e.g., Python) and time/space complexity analysis.