Cherry Blossom Ending

Interview

Time limit3sMemory limit1024 MB

Summary

Given N cherry trees with bloom periods over M days, find the longest run of adjacent trees blooming together on any day and how many days reach that length.

Level: Medium6 of 10
Topics: Segment tree, Sorting, Implementation
Solved: No attempts yet

Problem

Source: 윤찐빵

A cherry blossom festival to celebrate UDPC was held in UDP Village! The festival lasts $M$ days, and $N$ trees stand in a row at the festival site. The trees are numbered 1 to $N$ in order. The $i$ -th cherry tree blooms from day $S_i$ to day $E_i$ of the festival. Cherry blossoms look better when they are clustered, so Yoon, Dalgu, and Phoenix want to go flower viewing on a day when the most cherry trees are blooming in a row. On a given day, trees $a$ through $b$ are blooming in a row if all of them are in bloom that day. The number of cherry trees blooming in a row on a day is the maximum length $b-a+1$ over such intervals $[a, b]$ . For the three mascots who are looking forward to the festival, find the maximum number of cherry trees blooming in a row during the festival period, and the number of days on which that maximum occurs.

Input

The first line contains the number of cherry trees $N$ and the festival period $M$ , separated by a space. ( $1\leq N\leq 10^5;1\leq M\leq 10^9$ )

From line 2 to line $N+1$ , line $i+1$ contains $S_i$ and $E_i$ , separated by a space, which give the period during which the $i$ -th cherry tree is in bloom. ( $1\leq S_i\leq E_i\leq M$ )

Output

Print the maximum number of cherry trees blooming in a row during the festival period, and the number of days on which the most cherry trees are blooming in a row, separated by a space, in that order.

Examples3

Example 1
Input
```
3 5
3 5
1 3
1 1
```
Expected output
```
2 2
```
Example 2
Input
```
5 10
8 10
6 9
1 3
5 9
1 8
```
Expected output
```
2 5
```
Example 3
Input
```
3 3
1 1
2 2
3 3
```
Expected output
```
1 3
```