Sharing is caring! This weekend, the RSP graduates are visiting the The University of Adelaide to impart their computer science knowledge.

You've managed to book out ~n~ lecture halls, numbered from ~1~ to ~n~, which can support two lectures each. There are ~m~ graduates who want to give a single lecture about a particular topic, but each graduate can only access some subset of room numbers. Additionally, to keep things interesting, two lectures cannot use the same lecture hall if their topics are rotationally equivalent.

A string ~S~ can be rotated by moving some number of characters from the start of the string to the end, keeping their original order. For example, rotating HELLOWORLD by ~5~ positions produces WORLDHELLO. Two strings are considered rotationally equivalent if one can be obtained from the other in this way.

What is the maximum number of lectures you are able to host at the university?

Input

The first line contains two integers, ~n~ and ~m~, ~(1 \leq n, m \leq 1000)~, the number of lecture halls, and the number of lectures the students want to deliver.

The next ~m~ lines contain a string ~S~ ~(1 \leq |S| \leq 500)~, an integer ~k~ ~(1 \leq k \leq 100)~, and then ~k~ more integers ~h_1, \dots, h_k~ ~(1 \leq h_i \leq n)~, where ~S~ represents the topic for one graduate's lecture, ~k~ is the number of rooms they have access to, and ~h_1, \dots, h_k~ are the room numbers they have access to.

Output

Output the maximum number of lectures that can be delivered.

Example

Input 1

3 6
HOWTORSP 2 1 2
RSPHOWTO 2 2 3
FLOWCUT 2 1 3
CUTFLOW 2 1 3
INTROTOAUCPL 1 1
OUTROTOAUCPL 1 3

Output 1

5

There are ~3~ lecture halls and ~6~ students who want to do the following lectures:

Rotationally equivalent to HOWTORSP:

• HOWTORSP, in room ~1~ or ~2~.
• RSPTOHOW, in room ~2~ or ~3~.

Rotationally equivalent to FLOWCUT:

• FLOWCUT, in room ~1~ or ~3~.
• CUTFLOW, in room ~1~ or ~3~.

Rotationally equivalent to INTROTOAUCPL:

• INTROTOAUCPL, in room ~1~.

Rotationally equivalent to OUTROTOAUCPL:

• OUTROTOAUCPL, in room ~1~.

We can do the following allocation:

• Room ~1~: HOWTORSP and FLOWCUT
• Room ~2~: RSPTOHOW only.
• Room ~3~: INTROTOAUCPL and CUTFLOW
• OUTROTOAUCPL can't be ran.

Therefore, a total of ~5~ lectures can be ran. It can be shown that this is the maximum number for this case.

Input 2

4 9
CAB 2 1 2
AB 2 1 2
BA 2 3 4
CAB 2 1 2
BA 2 3 4
BCA 2 1 2
UNIQUE 4 1 2 3 4
AB 2 2 3
ABC 4 1 2 3 4

Output 2

8

Input 3

3 5
AAA 3 1 2 3
AAA 3 1 2 3
AAA 3 1 2 3
AAA 3 1 2 3
AAA 3 1 2 3

Output 3

3