enigma is hiring new admins to maintain PNOJ while he goes on vacation to Wuhan during the break!

PNOJ has \(M\) different staff positions, numbered \(1\) to \(M\). Each staff position can only be occupied by one person.

Since enigma is in a hurry, he doesn't have time to evaluate the administrative abilites of all \(N\) people each applying for some subset of the \(M\) total positions (That would take \(O(MN)\)!).

Instead, help him determine the maximum amount of positions that can be filled from the \(N\) people.

For 10% of the points, \(1\le N, M\le 10\).

The first line contains \(N\) (\(1\le N\le 100`\)) and \(M\) (\(1\le M\le 100\)), followed by \(N\) lines.

The ith line contains \(S_i\) (\(0\le Si\le M\)), the number of positions the \(i\)th staff member is applying for, followed by \(S_i\) integers, the positions.

Output on one line the maximum number of positions enigma can fill by hiring each person for at most one position.

`6 6`

2 2 3

0

2 1 4

1 3

2 3 4

1 6

`5`

- Points: 17
- Time limit: 1.5s
- Memory limit: 64.0M
- Author: BattleMage_
- Category: Classics
- Type: Dynamic Programming, Graph Theory
- All Submissions Best Submissions

Comments

- There are no comments.