Mount Allison Programming Showdown 2019

Start

2019-03-16 17:00 CET

Mount Allison Programming Showdown 2019

End

2019-03-16 22:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -269 days 6:58:08

Time elapsed

5:00:00

Time remaining

0:00:00

Problem J
Piano Lessons

/problems/pianolessons/file/statement/en/img-0001.jpg
Mrs. Mackenzie loves teaching piano. She started last year with just five students in her home studio at Green Gables in the beautiful province of Prince Edward Island (Canada). Pretty soon, kids across the entire province heard about her brilliant piano teaching, and now she is receiving hundreds of calls requesting lessons. She is finding it very difficult to fit them all into her schedule since she has a limited number of time slots and students have varying availability. While she is baffled by some kids’ irrational interest in sports, she respects their prior commitments.

Given Mrs. Mackenzie’s time slots, and a list of the time slots that work for each potential student, can you help her determine the maximum number of students she can fit into her schedule? Note that Mrs. Mackenzie only teaches private lessons (one student at a time) and no student requires more than one time slot.

Input

The first line of input contains two space-separated integers, $N$ and $M$, where $N$ is the number of potential students and $M$ is the number of time slots that Mrs. Mackenzie has available ($1 \leq N, M \leq 1\, 000$). These time slots are numbered $1, 2, 3, \ldots , M$. This is followed by $N$ lines, one for each potential student. Each of these $N$ lines begins with an integer $T$, the number of time slots that work for the student ($0 \leq T \leq M$), and this is followed (on the same line) by $T$ distinct space-separated integers $t_ i$, representing the specific time slots that work ($1 \leq t_ i \leq M$).

Output

Output the maximum number of students Mrs. Mackenzie can fit into her $M$ time slots.

Sample Input 1 Sample Output 1
2 3
1 3
1 3
1
Sample Input 2 Sample Output 2
5 5
1 1
3 1 2 3
3 1 3 4
3 2 4 5
3 2 3 5
5