Sea Voyage
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.
Input
The input begins with two numbers, N and K (1 ≤ N ≤ 16, 1 ≤ K ≤ 100), representing the number of boats and the number of people, respectively. This is followed by N lines, each containing two numbers: s and c (0 ≤ s ≤ 100, 0 ≤ c ≤ 10^6), where s is the number of seats on the boat and c is the cost of one ticket. Next, there are K lines, each starting with the number t, which indicates how many boats are suitable for the current person, followed by a list of these boat numbers. All numbers range from 1 to N, and each number appears at most once per list.
Output
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.