Job Assignment 3

Time limit3sMemory limit256 MB

Summary

Each worker takes jobs only from a given eligible list, with K workers allowed two jobs, to finish as many of M jobs as possible.

Level: Medium4 of 10
Topics: Graph
Solved: No attempts yet

Problem

Gangho's company has $N$ employees and $M$ jobs to finish. Employees are numbered 1 to $N$ , and jobs are numbered 1 to $M$ .

Each employee takes one job out of the jobs that employee can do, and each job is taken by one employee. $K$ of the $N$ employees can take up to two jobs.

Given the list of jobs each employee can do, write a program that finds the largest number of the $M$ jobs the company can finish.

Input

The first line contains the number of employees $N$ , the number of jobs $M$ , and the number of employees who can take two jobs $K$ . ( $1 \le N, M \le 1000$ , $1 \le K \le N$ )

Each of the next $N$ lines describes one employee. The $i$ -th line contains the number of jobs employee $i$ can do, followed by the numbers of those jobs.

Output

Print the largest number of jobs Gangho's company can finish.

Note

In the first example, employee 1 takes two jobs. Employee 1 takes jobs 1 and 2, employee 2 takes job 3, and employee 3 takes job 5, so four jobs are finished.

Examples4

Example 1
Input
```
5 5 1
3 1 2 3
3 1 2 3
1 5
1 5
1 5
```
Expected output
```
4
```
Example 2
Input
```
1 1 1
1 1
```
Expected output
```
1
```

Example 3

Input

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

Expected output

Example 4
Input
```
3 5 2
3 1 2 3
1 4
2 4 5
```
Expected output
```
4
```