April Fools

Interview

Time limit1sMemory limit1024 MB

Summary

Each newspaper prints exactly one false fact. Find the smallest and largest total number of false facts that can be consistent with this.

Level: Medium4 of 10
Topics: Brute force, Bit manipulation
Solved: No attempts yet

Problem

On April Fools Day newspapers like to fool their readers by publishing false and usually absurd facts. For example, a fact stating that today Vilnius television tower was brought down by wind.

You are given a range of facts which were published by each of the $N$ different newspapers. These facts are denoted by natural numbers from $1$ to $F$ . For example:

Newspaper 1: 1, 2, 5
Newspaper 2: 2, 3, 4
Newspaper 3: 1, 6

You also know that this April Fools Day each of the newspapers published exactly one false fact.

Find the smallest and the biggest number of false facts that could have been published today.

Input

The first line contains two integers $N$ and $F$ , separated by a space.

The facts published by each newspaper are described on the remaining $2N$ lines. On line $2i$ , the number $k_i$ is given, the count of facts published by the $i$ -th newspaper ( $1 \le k_i \le F$ ). On line $2i+1$ , the $k_i$ integers $f_{ij}$ are given, separated by spaces, with $1 \le f_{ij} \le F$ and $f_{ij} < f_{i(j+1)}$ . Every fact from $1$ to $F$ is published by at least one newspaper.

Output

Print two numbers separated by a space: the smallest and the biggest number of false facts that could have been published that day.

Constraints

$1 \le N \le 200$
$1 \le F \le 20$

Examples1

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