Description

Original Source: APIO 2007

The newly built Circular Zoo is the pride of the Asia-Pacific region. The zoo is located on a small island in the Pacific Ocean and consists of a large circular enclosure with each section containing a unique animal, as shown in the following illustration:

You are the public relations officer of the zoo. Your task is to ensure that every visitor enjoys their time at the zoo as much as possible. Today, a group of children is visiting, and you want them to have a wonderful experience. However, this is not easy—some children like certain animals, while others are afraid of some. For example, Alex likes cute monkeys and koalas but is afraid of lions with sharp teeth. Polly, on the other hand, likes lions for their beautiful manes but dislikes koalas because of their smell.

You can choose to remove some animals from their enclosures so that the children won't be scared. However, you cannot remove too many animals, or there will be very few left for the children to see.

Each child stands outside the large circular enclosure and can see five consecutive enclosures. You have gathered information about which animals each child likes and fears. A child will be happy if either of the following conditions is met:

• At least one animal they fear is removed;
• At least one animal they like is not removed.

For example, consider the following scenario with children and animals:

If you remove the animals from enclosures 4 and 12, Alex and Ka-Shu will be happy because at least one animal they fear has been removed. This will also make Chaitanya happy because the animals he likes in enclosures 6 and 8 remain. However, Polly and Hwan will be unhappy because they cannot see any animals they like, and the animals they fear are still there. This arrangement makes three children happy.

Alternatively, if you remove the animals from enclosures 4 and 6, Alex and Polly will be happy because the animals they fear have been removed. Chaitanya will also be happy because, although the animal he likes in enclosure 6 has been removed, he can still see the animal he likes in enclosure 8. Similarly, Hwan will be happy to see the animal he likes in enclosure 12. The only unhappy child will be Ka-Shu.

If you only remove the animal from enclosure 13, Ka-Shu will be happy because one animal he fears has been removed. Alex, Polly, Chaitanya, and Hwan will also be happy because they can all see at least one animal they like. Thus, five children will be happy. This method maximizes the number of happy children.

Input Format

The first line of input contains two integers, $N$ and $C$, separated by a space. $N$ is the number of enclosures, and $C$ is the number of children. The enclosures are numbered clockwise as $1, 2, 3, \ldots, N$.

The next $C$ lines each describe a child in the following format: $E \ F \ L \ X_1 \ X_2 \ \cdots X_F \ Y_1 \ Y_2 \ \cdots Y_L$.

Here, $E$ represents the first enclosure the child can see. In other words, the child can see enclosures $E, E+1, E+2, E+3, E+4$. Note that if the numbering exceeds $N$, it wraps around starting from 1. For example, when $N=14$ and $E=13$, the child can see enclosures $13, 14, 1, 2,$ and $3$.

$F$ is the number of animals the child fears, and $L$ is the number of animals the child likes.

Enclosures $X_1, X_2, \ldots, X_F$ contain animals the child fears, and enclosures $Y_1, Y_2, \ldots, Y_L$ contain animals the child likes.

$X_1, X_2, \ldots, X_F, Y_1, Y_2, \ldots, Y_L$ are all distinct integers, and all the enclosures listed are visible to the child.

The children are already sorted in ascending order based on the first enclosure they can see (so the child with the smallest $E$ comes first, and the one with the largest $E$ comes last).

Note that there may be multiple children with the same $E$.

Output Format

Output a single integer representing the maximum number of children that can be made happy.

Sample 1

Sample 1 corresponds to the scenario described earlier, where all children ($C=5$) are made happy.

14 5
2 1 2 4 2 6
3 1 1 6 4
6 1 2 9 6 8
8 1 1 9 12
12 3 0 12 13 2

5

Sample 2

Sample 2 presents a situation where it is impossible to make all children ($C=7$) happy.

12 7
1 1 1 1 5
5 1 1 5 7
5 0 3 5 7 9
7 1 1 7 9
9 1 1 9 11
9 3 0 9 11 1
11 1 1 11 1

6

Data Range and Hints

For each test case, if your answer is correct, you will receive full points; otherwise, you will receive 0 points.

For all data, $10 \le N \le 10^4$, $1 \le C \le 5 \times 10^4$, and $1 \le E \le N$.