The Cost of a Walk
There are several boats and a large group of people. Each boat has a known capacity, and each person has a preference for which boats they would like to ride. Based on previous experiences, the boat owners realized that their previous payment method was not profitable. Therefore, they decided to charge a fixed fee for each boat used, regardless of the number of passengers on board. Your task is to assign people to boats for a single sea trip in a way that minimizes the number of boats used.
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 a single number s (0 ≤ s ≤ 100), indicating the seating capacity of each boat. Next, there are K lines, each starting with a number t, which is the count of boats suitable for the current person, followed by a list of these boat numbers. All numbers are within the range from 1 to N, and each number appears at most once in the list.
Output
Output a single number, which is the minimum number of boats needed. If it is impossible to accommodate all the people on the boats, output -1.