Zoo

A new circular zoo, the pride of the Asia-Pacific region, has just been built on a small island in the Pacific. Its animal cages are arranged in one big circle, and each cage holds a single, distinct animal.

The goal is to make as many visiting children as possible enjoy their visit. This is not easy: some children love certain animals while others are frightened by them. For example, Alex loves monkeys and koalas because they are cute but is scared of lions because of their sharp teeth, while Polly loves lions for their beautiful manes but dislikes koalas because of their awful smell.

We may move some of the animals that children fear to another zoo (that is, empty those cages). But moving too many is bad, because then there would be nothing left to look at. We want to choose which animals to move so that as many children as possible are happy.

Each child stands outside the circle and watches only the animals in the 5 consecutive cages directly in front of them. For each child, the list of animals they fear and the list they like are given. A child is happy if at least one of the following holds:

• at least one of the animals they fear (among the ones they watch) has been moved away;
• at least one of the animals they like (among the ones they watch) still remains.

For example, suppose five children are described by the table below.

• If the animals in cages 4 and 12 are moved: Alex and Ka-Shu are happy because a feared animal was moved, and Chaitanya is happy because the liked animals in cages 6 and 8 remain. Polly and Hwan are not happy, because all of their liked animals were moved and none of their feared animals were. So 3 children are happy.
• If the animals in cages 4 and 6 are moved: Alex and Polly are happy because a feared animal was moved; Chaitanya is happy because the liked animal in cage 8 remains, and Hwan because the liked animal in cage 12 remains. Only Ka-Shu is unhappy, so 4 children are happy.
• If instead only the animal in cage 13 is moved: Ka-Shu is happy because a feared animal was moved, and each of the other four children still has at least one liked animal remaining, so all are happy. This gives the maximum of 5 happy children.

Find the maximum number of children that can be happy at the same time.

The first line contains two integers $N$ and $C$. $N$ ($10 \le N \le 10000$) is the number of cages and $C$ ($1 \le C \le 50000$) is the number of children. The cages are numbered $1, 2, \ldots, N$ clockwise around the circle.

Then $C$ lines follow, each describing one child's watched cages, feared animals, and liked animals in the following format.

E F L X1 X2 ... XF Y1 Y2 ... YL

where:

• $E$ is the number of the first cage the child watches ($1 \le E \le N$); that is, the child watches cages $E, E+1, E+2, E+3, E+4$. If a number exceeds $N$ it wraps back to $1$. For example, if $N = 14$ and $E = 13$, the watched cages are $13, 14, 1, 2, 3$.
• $F$ is the number of feared animals and $L$ is the number of liked animals.
• $X_1, \ldots, X_F$ are the cage numbers of the feared animals ($1 \le X_i \le N$).
• $Y_1, \ldots, Y_L$ are the cage numbers of the liked animals ($1 \le Y_i \le N$).

$X_1, \ldots, X_F, Y_1, \ldots, Y_L$ are all distinct, and every one of them is a cage that this child watches.

The children are given in nondecreasing order of $E$ (the child with the smallest $E$ first, the largest $E$ last). Note that two or more children may share the same value of $E$.

Print a single integer: the maximum number of children that can be happy at the same time.