To celebrate over ~200~ problems written at AUCPL.inc, you and your fellow junior problemsetters are going to hold a dinner! They say that too many chefs makes a messy kitchen, but we aren't going to let some silly idiom get in the way.

There are many preparation tasks (such as chopping, peeling, and grilling) that must be completed for the dinner to be a success. You may select a subset of employees to help carry out these tasks.

Each employee is capable of handling either ~1~ or ~2~ tasks.

Since all employees would also like time to enjoy the dinner, you must choose a subset of employees such that every task is handled by at least one selected employee, while minimising the number of selected employees.

How many problemsetters are needed in this kitchen?

Input

The first line contains two integers ~n~ and ~m~ (~1 \leq n, m \leq 100~), the number of tasks that need to be completed, and the number of employees who are willing to help out.

The next line contains ~n~ unique strings ~S~ ~(1 \leq |S| \leq 10)~, the names of the tasks that need to be completed for the dinner to be successful. These can contain any printable ASCII characters.

Each of the next ~m~ lines describes an employee in form ~k\ S_1\ S_2~, where:

• ~k~ is the number of tasks the employee can handle (~1~ or ~2~),

• ~S_1~ and optionally ~S_2~ are the tasks they can perform. If ~k = 1~, then only ~S_1~ is given.

Output

Output the minimum number of AUCPL.inc employees needed to complete all tasks. It is always possible to complete all tasks with some number of employees.

Examples

Input 1

5 6
Cooking Roasting Grilling Frying Toasting
2 Cooking Grilling
1 Frying
2 Roasting Toasting
2 Roasting Grilling
2 Roasting Frying
1 Toasting

Output 1

3

Employees can be selected as shown below.

Input 2

6 5
MakingA MakingB MakingC MakingD MakingE MakingF
2 MakingA MakingC
2 MakingB MakingD
2 MakingE MakingD
2 MakingC MakingF
2 MakingE MakingF

Output 2

3

Input 3

5 5
Common1 Common2 Common3 Unique1 Unique2
1 Unique1
1 Unique2
2 Common1 Common2
2 Common2 Common3
2 Common3 Common1

Output 3

4