Sea Voyage#3647
There are several boats and a large group of people. Each boat has a known capacity and ticket price. For each person, we know which boats they prefer to ride. The goal is to assign people to boats for a single sea trip in such a way that the total ticket cost is minimized.
The input begins with two numbers, and (1 \le N \le 16, 1 \le K \le 100), representing the number of boats and the number of people, respectively. This is followed by lines, each containing two numbers: and (0 \le s \le 100, 0 \le c \le 10^6), where is the number of seats on the boat and is the cost of one ticket. Next, there are lines, each starting with the number , which indicates how many boats are suitable for the current person, followed by a list of these boat numbers. All numbers range from to , and each number appears at most once per list.
Output a single number representing the total cost of one trip, or -1 if it is not possible to seat all people on the boats.
Example 1