Job Assignment at Kangho's Company

Time limit2sMemory limit256 MB

Summary

Assign each employee at most one job they can do so the number of finished jobs is largest, then maximize the total salary over those assignments.

Level: Medium7 of 10
Topics: Graph, Shortest path
Solved: No attempts yet

Problem

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

Each employee can take at most one job, and only from the list of jobs that employee can do. Each job is taken by at most one employee. Some employees may end up with no job.

For every employee you are given the list of jobs that employee can do and the salary Kangho must pay for each of them. Write a program that finds how many of the $M$ jobs can be finished at most, and the largest total salary Kangho 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_i$ ( $0 \le k_i \le M$ ), the number of jobs employee $i$ can do, followed by $k_i$ pairs of numbers. Each pair is a job number and the salary that must be paid when employee $i$ takes that job. A salary is 0 or a natural number no greater than 10,000.

Output

On the first line, print the largest number of jobs that Kangho's company can finish.

On the second line, print the largest total salary Kangho must pay among the assignments that finish that many jobs.

Examples2

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
23

Example 2
Input
```
2 2
2 1 100 2 1
1 1 50
```
Expected output
```
2
51
```