Hide

Problem J
Don't Be Fake

DontBeFake is an app where people get a notification at a random point in time, and they have to take a picture of what they are doing right now.

You have $N$ friends on DontBeFake. Each friend has a set of intervals of seconds $[L, R]$ when they are available. If they get a notification at second $s$ and they are available, they will take a picture and you will get to see it. Because the DontBeFake app is slow and so is taking a picture, even if they are available a second later, they will not have time to take the picture. All friends live in the same time zone and will get one notification at exactly the same time in the day. All times are specified as seconds from midnight.

You want to know what is the maximum number of pictures you can view in the day, over all possible seconds that the notification can arrive. In addition, you also want to know how many different seconds the notification could arrive for the maximum number of pictures to be taken.

Input

Input begins with a line containing the integer $N$ ($1 \leq N \leq 50$). The next $N$ lines each describes the set of available intervals for the $N$ friends. Each such line starts with an integer $M$ ($1 \leq M \leq 10$) followed by $M$ pairs of integers $L_ i$, $R_ i$ ($L_ i \leq R_ i$) meaning that the friend is available between $L_ i$ and $R_ i$ seconds, inclusive. It is guaranteed that $R_ i < L_{i+1}$ for all $1 \leq i < M$, so that the intervals do not overlap. It is also guaranteed that $0 \leq L_ i, R_ i < 86\, 400$.

Output

Output on the first line the maximum number of pictures you can view in the day. On the second line, output the total number of seconds the notification could arrive for the maximum number of pictures to be taken.

Sample Input 1 Sample Output 1
3
1 0 20000
2 10000 20000 40000 60000
1 15000 80000
3
5001
Sample Input 2 Sample Output 2
3
1 0 10000
2 10000 20000 30000 40000
2 20000 30000 50000 80000
2
3

Please log in to submit a solution to this problem

Log in