Under construction

Still being built. Things may change

Don't Be Fake

Interview

Time limit1sMemory limit1024 MB

Summary
Given each friend's available second intervals, find the maximum number of friends who can photograph one notification second and count the seconds that reach it.
Level

Easy3 of 10

Topics
Prefix sum, Array
Solved
No attempts yet

Problem

DontBeFake is an app that sends each user a notification at a random moment. The user then has to photograph what they are doing at that exact moment.

You have NN friends on DontBeFake. Each friend has a set of time intervals [L,R][L, R] when they are available. If a friend gets a notification at second ss and ss falls inside one of their available intervals, they take a picture, and you get to view it. The app and taking a picture are both slow, so a friend who becomes available only one second after ss does not have time to take the picture.

All friends live in the same time zone and get one notification at exactly the same time of day. All times are seconds from midnight.

Find the maximum number of pictures you can view in the day, over all seconds when the notification can arrive. Also find how many different seconds the notification could arrive at so that the maximum number of pictures is taken.

Input

The first line contains an integer NN (1≤N≤501 \leq N \leq 50). Each of the next NN lines describes the available intervals of one friend. Each such line starts with an integer MM (1≤M≤101 \leq M \leq 10), followed by MM pairs of integers LiL_i, RiR_i (Li≤RiL_i \leq R_i). This means the friend is available from second LiL_i to second RiR_i, inclusive.

It is guaranteed that Ri<Li+1R_i < L_{i+1} for all 1≤i<M1 \leq i < M, so the intervals do not overlap. It is also guaranteed that 0≤Li,Ri<86 4000 \leq L_i, R_i < 86\,400.

Output

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

Examples2

  1. Example 1

    Input
    3
    1 0 20000
    2 10000 20000 40000 60000
    1 15000 80000
    
    Expected output
    3
    5001
    
  2. Example 2

    Input
    3
    1 0 10000
    2 10000 20000 30000 40000
    2 20000 30000 50000 80000
    
    Expected output
    2
    3