Once Agent Ω figured out how to shut down the torpedo A.I. system

The description provided for this problem:

Once Agent Ω figured out how to shut down the torpedo A.I. system, she was ready to invade the C.H.I.M.E.R.A. warship and stop The Serpent once and for all.  After scanning the warship she figures out that she'll need a team of agents with her with a particular set of skills.  Can you help her decide which agents to take to make sure that the team is as small as possible, but all of the needed skills are represented?

NOTE: For this problem, your program must be guaranteed to output the correct answer (or timeout in the process of searching). If your program outputs an incorrect response for any test case, it will receive 0 credit on this problem (regardless of how many other test cases it passes). Timing out is allowed, however. Test cases on which you time out will not provide points, but will also not zero out points earned on test cases where your program returned the correct output. You do not need to complete all of the test cases within the time limit to get full credit (400 points counts as full credit for this problem - any points beyond that are extra credit). Note also that the test cases get substantially more difficult as you go into the extra credit range.

Input Format

The first line has two values,  N and K.

N represents the number of candidate agents for the mission, and K  is the number of distinct skills that (combined) the candidates must possess.

The second line has K words on it, listing the specific skills that are required.

The next N pairs of lines each provide information about a single person.

The first line in the pair for person i indicates the number of skills that person knows (Pi ), and the second line lists those Pi  specific skills.

Constraints

1 ≤ N ≤ 200
1 ≤ K ≤ 200
0 ≤ Pi  ≤ K

Output Format

You must output a single value indicating the fewest people that you can choose for the mission while having all of the needed skills rerpesented.

Example 0
Sample Input

5 6
Botany Neuroscience ArtificialLife Batteries Metals InformationTheory
3
Botany Neuroscience ArtificialLife
2
Botany Batteries
1
Botany
4
Botany Batteries Metals InformationTheory
3
Neuroscience Batteries InformationTheory
Sample Output

2
Explanation

Five people are available to cover six required skills.

Only two of the people are needed. The first person (who provides Botany, Neuroscience, and ArtificialLife) and the fourth person (who provides Batteries, Metals, and InformationTheory, as well as duplicating Botany). No smaller answer is possible since no single person has all six skills.

Example 1
Sample Input

10 8
Plastics Fermentation Ceramics InformationTheory CloudComputing EnvironmentalScience Biometrics PlasmaPhysics
4
Plastics Fermentation Ceramics InformationTheory
4
Plastics Fermentation CloudComputing EnvironmentalScience
4
Plastics Ceramics Biometrics PlasmaPhysics
4
Plastics Fermentation Ceramics CloudComputing
4
Plastics Fermentation Ceramics EnvironmentalScience
4
Fermentation Ceramics InformationTheory CloudComputing
4
Fermentation InformationTheory EnvironmentalScience PlasmaPhysics
4
Ceramics InformationTheory CloudComputing Biometrics
4
InformationTheory CloudComputing Biometrics PlasmaPhysics
4
InformationTheory CloudComputing EnvironmentalScience PlasmaPhysics
Sample Output

2
Explanation

10 People are available to cover eight skills.

It is possible to use only two people: The fifth person knows Plastics, Fermentation, Ceramics, and EnvironmentalScience. The ninth person knows InformationTheory, CloudComputing, Biometrics, and PlasmaPhysics. No tasks are duplicated across both selected people.