Minimum Cost to Satisfy Features

Given a set of required features and several subscription plans, each plan having a cost and a set of features it provides, determine the minimum total cost required to cover all the required features. You are allowed to select any combination of plans. If it is not possible to cover all the required features using the available plans, output $-1$.

Note: The problem may require examining all possible combinations of plans (using brute force or bitmasking) because a plan can contribute to fulfilling multiple required features.

Mathematical formulation: Let $R$ be the set of required features and each plan $i$ is associated with a cost $c_i$ and a set of features $S_i$. Find a selection of plans $I$ such that $\bigcup_{i \in I} S_i \supseteq R$, and the sum $\sum_{i \in I} c_i$ is minimized.

inputFormat

Input is given via standard input (stdin) and consists of multiple test cases. For each test case:

1. The first line contains a string of required features separated by spaces.
2. The second line contains an integer $n$, the number of subscription plans.
3. The following $2n$ lines describe the subscription plans. Each plan is given by two consecutive lines: the first line contains an integer cost, and the second line contains a space‐separated list of features provided by that plan.

The input terminates when the line containing the required features is "0".

outputFormat

For each test case, output on a separate line the minimum total cost needed to cover all required features. If it is not possible to cover all required features, output -1.## sample

featureA featureB
3
30
featureA featureC
20
featureB featureD
25
featureA featureB featureD
featureA featureC featureD
2
50
featureA
20
featureC featureD
0

25
70