Assigning Jobs 5

Time limit2sMemory limit256 MB

Summary

Assign each employee at most one job they can do so the number of finished jobs is largest and the total salary is smallest.

Level: Medium7 of 10
Topics: Graph, Shortest path
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 handles at most one of the jobs that employee can do, and no job is handled by more than one employee. When an employee handles a job, Gangho pays that employee the salary fixed for that job.

You are given the list of jobs each employee can do together with the salary for each of them. Write a program that finds the largest number of jobs the company can finish, and the smallest total salary Gangho pays among the assignments that finish that many jobs.

Input

The first line contains the number of employees $N$ and the number of jobs $M$ . ( $1 \le N, M \le 400$ )

Each of the next $N$ lines describes one employee. Line $i$ starts with $K$ , the number of jobs employee $i$ can do, followed by $K$ pairs, each of which is a job number and the salary for that job. $K$ is between 0 and $M$ , and no employee lists the same job twice. Every salary is an integer between 0 and 10,000.

Output

On the first line, print the largest number of jobs the company can finish.

On the second line, print the smallest total salary among the assignments that finish that many jobs.

Examples6

Example 1

Input

5 5
2 1 3 2 2
1 1 5
2 2 1 3 7
3 3 9 4 9 5 9
1 1 0

Expected output

4
18

Example 2
Input
```
1 1
1 1 0
```
Expected output
```
1
0
```
Example 3
Input
```
1 1
0
```
Expected output
```
0
0
```
Example 4
Input
```
3 1
1 1 7
1 1 3
1 1 5
```
Expected output
```
1
3
```
Example 5
Input
```
4 4
1 1 0
1 2 0
1 3 0
1 4 0
```
Expected output
```
4
0
```
Example 6
Input
```
1 5
5 1 9 2 4 3 7 4 4 5 6
```
Expected output
```
1
4
```