Maximizing Happy Kids in the Circular Zoo

A new circular zoo is the pride of the Asia‐Pacific region. The zoo is arranged in a circle on a small Pacific island with n enclosures numbered from 1 to n in order. Each enclosure houses one species of animal. A group of kids comes to visit the zoo. Each kid stands outside the main fence and can see exactly 5 consecutive enclosures (wrapping around the circle if necessary).

Each kid has two sets of preferences regarding the animals in his view:

• The kid likes some animals. He will be happy if at least one of the animals he likes remains (i.e. is not removed).
• The kid fears some animals. He will also be happy if at least one of the animals he fears has been removed.

You are in charge of the zoo. You may remove the animal from any enclosure. However, because the zoo’s attractions are important, you cannot remove too many animals; you want to maximize the number of happy kids while keeping most animals on display. (Note that a kid is happy if either condition is met.)

Each kid’s visible window is determined by a starting enclosure index s. His window then consists of enclosures: \[ s,\; ((s+1)\bmod n)\; ,\; ((s+2)\bmod n),\; ((s+3)\bmod n),\; ((s+4)\bmod n) \] (with the convention that enclosure numbers are in \(\{1,2,\dots,n\}\) and modular arithmetic is used so that after n comes 1).

You are given the information for m kids. For each kid, you know:

1. The starting index s for his visible window.
2. The list of enclosures (which are a subset of the 5 enclosures in his window) that he likes.
3. The list of enclosures (again, from his window) that he fears.

Your task is to choose a set of enclosures from which to remove the animals in order to maximize the total number of happy kids. A kid is happy if at least one of the following holds within his window: \[ \text{(i) }\exists\, i \in \text{fear set: animal at } i \text{ is removed} \quad \text{or}\quad \text{(ii) }\exists\, j \in \text{like set: animal at } j \text{ is not removed.} \]

Output the maximum number of happy kids you can achieve.

inputFormat

The first line contains two integers n and m (n is the total number of enclosures, m is the number of kids).

Then, for each kid, the input is given as follows:

1. A line with an integer s (1 ≤ s ≤ n), the starting enclosure index of his visible window.
2. A line with two integers a and b, indicating the number of enclosures the kid likes and the number he fears respectively (0 ≤ a, b ≤ 5).
3. If a > 0, a line with a distinct integers representing the enclosure numbers (from his window) that he likes.
4. If b > 0, a line with b distinct integers representing the enclosure numbers (from his window) that he fears.

The 5 enclosures visible to the kid are the ones starting from s and the next 4 consecutive enclosures in circular order.

outputFormat

Output a single integer – the maximum number of happy kids possible.

sample

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

5