Fax McClad, Croneria's most meticulous bounty hunter, is going to prepare a dish for Thanksgiving! Fax prepared a turkey last year, so this year, he will cook something different.
There are different food items, numbered from to . There are different recipes. A recipe consists of a non-empty list of items that need to be combined to produce a target item. Only one unit of each item in the list is required, and the target item will not be in the list. Additionally, no two recipes will have the same target item, each item will appear at most once as a required item in a recipe, and item will not appear as a required item.
Fax wants to have one unit of item as his dish. For each item , he currently has units of that item.
Dankey Kang, Fax's enemy, wants to ruin Fax's Thanksgiving, so he will steal some food items from Fax so that he cannot have item . What is the minimum number of items that Dankey Kang must take?
|1||10||There is exactly item, i.e.,|
The first line will contain integers and .
Each of the next lines will contain one recipe. A recipe is one line long and follows this format:
- The first integer is the target item.
- The second integer is the number of required items.
- The remaining integers are the required items.
The last line will contain integers. The integer in this line is .
Sample Input 1
8 3 1 2 4 5 4 2 2 3 5 2 6 7 1 2 1 1 3 0 0 10
Sample Output 1
Explanation for Sample Output 1
Dankey Kang can steal item , item , and item . Afterwards, Fax cannot have item by following the recipes.
It is not possible to ruin Fax's Thanksgiving by stealing items. For example, if Dankey Kang stole item and item , the food list will become
0 2 1 0 3 0 0 10. Fax can follow the second recipe, and then the first recipe, to produce item .
Sample Input 2
3 2 2 1 3 3 1 2 0 0 1
Sample Output 2