Magic Potion

Problem Source

ICPC Nanjing 2018 I

Problem Description

There are $n$ heroes and $m$ monsters living in an island. The monsters became very vicious these days, so the heroes decided to diminish the monsters in the island. However, the $i$-th hero can only kill one monster belonging to the set $M_i$. Joe, the strategist, has $k$ bottles of magic potion, each of which can buff one hero's power and let him be able to kill one more monster. Since the potion is very powerful, a hero can only take at most one bottle of potion.

Please help Joe find out the maximum number of monsters that can be killed by the heroes if he uses the optimal strategy.

Input Format

The first line contains three integers $n, m, k\ (1 \le n, m, k \le 500)$ indicating the number of heroes, the number of monsters and the number of bottles of potion.

Each of the next $n$ lines contains one integer $t_i$, the size of $M_i$, and the following $t_i$ integers $M_{i, j}\ (1 \le j \le t_i)$, the indices ($1$-based) of monsters that can be killed by the $i$-th hero $(1 \le t_i \le m,\ 1 \le M_{i, j} \le m)$.

Output Format

Print the maximum number of monsters that can be killed by the heroes.

Sample Input 1

3 5 2
4 1 2 3 5
2 2 5
2 1 2

Sample Output 1

4

Sample Input 2

5 10 2
2 3 10
5 1 3 4 6 10
5 3 4 6 8 9
3 1 9 10
5 1 3 6 7 10

Sample Output 2

7