You are given a restaurant menu with n single items and m combo offers. Each single item i has a price p[i] (in cents). Each combo j specifies nonnegative quantities q[j][i] for each item and a total combo price c[j]. A customer order is a vector need[i] (nonnegative integers). You may purchase any number of single items and any number of combos, but you cannot exceed need[i] for any item. Return the minimum total cost to exactly satisfy the order. Sub-questions: 1) Describe an algorithm (e.g., DP or search with memoization), justify correctness, and analyze its time and space complexity in terms of n, the needs, and the number of offers. 2) Follow-up: If the order involves only three distinct item types (all other need[i] = 0), how would you optimize the solution beyond naive pruning? Be specific about state representation (e.g., a 3D DP/state graph), transition design, and the improved complexity. 3) What preprocessing/pruning would you apply to discard dominated or irrelevant combos/items, and how would you prove that such pruning preserves optimality?