Compute minimum-cost service cover

You are given: (1) a list of rental service packages, where each package contains a set of services (strings) and a non-negative price, e.g., [(["wifi"], 50), (["parking"], 30), (["parking", "tv"], 70)]; and (2) a list of required services, e.g., ["WiFi", "parking"]. Design and implement an algorithm that returns (a) the minimum total cost to cover all required services (treat service names case-insensitively), and (b) the combination (s) of package indices that achieve this minimum. Define the output as: min_cost: int and combos: List[List[int]] where each inner list is a strictly increasing list of package indices; if coverage is impossible, return (-1, []). Explain and analyze your approach, including time and space complexity in terms of N (packages) and S (distinct required services). Describe how you will reconstruct the optimal combination (s) from your DP/bitmask state; handle ties and avoid duplicate combinations. Provide tests for the example above and at least one case with no feasible cover.

Compute Minimum-Cost Service Cover

You are given a list of rental service packages and a list of required services. Each package is a pair (services, price), where services is a list of service names and price is a non-negative integer. Service names must be treated case-insensitively.

Write a function that returns all minimum-cost ways to cover every distinct required service.

Return a tuple (min_cost, combos):

• min_cost: the minimum total price needed to cover all required services
• combos: a list of package-index combinations that achieve min_cost

Rules:

• Package indices are 0-based.
• Each combo must be a strictly increasing list of indices.
• If multiple optimal combos exist, return all of them.
• Do not return duplicate combos.
• Ignore services in packages that are not required.
• If coverage is impossible, return (-1, []).
• For deterministic output, return combos sorted lexicographically.

A strong solution should use DP with bitmasking over the distinct required services, then reconstruct all optimal combinations by following only transitions that preserve the optimal cost.

Constraints

• 0 <= N <= 30, where N is the number of packages
• 0 <= price <= 10^6 for each package
• 0 <= S <= 15, where S is the number of distinct required services after case-insensitive normalization
• The number of optimal combinations can be exponential in N, so reconstruction is inherently output-sensitive

Examples

Example 1

Input: ([(["wifi"], 50), (["parking"], 30), (["parking", "tv"], 70)], ["WiFi", "parking"])
Output: (80, [[0, 1]])

Explanation: Package 0 covers wifi and package 1 covers parking for a total of 80. Package 2 does not include wifi, so using it with package 0 costs 120 and is not optimal.

Example 2

Input: ([(["wifi"], 50), (["tv"], 20)], ["wifi", "parking"])
Output: (-1, [])

Explanation: No package provides parking, so it is impossible to cover all required services.

Hints

1. Map each distinct required service to a bit position. Then each package becomes a bitmask showing which required services it covers.
2. Use DP on (package_index, remaining_services_mask) to compute the minimum cost, then run a DFS that follows only transitions whose cost matches the DP optimum to reconstruct all optimal combos.