3629. Channel On Live

单点时限: 3.0 sec

内存限制: 512 MB

EOJ has recently opened a new live channel, so that coders can broadcast their coding online and chat with the audience at the same time. It has become children’s favorite entertainment at night, well, other than the monthly contest.

It may sound hard to believe, but the EOJ team has recently encountered some trouble in terms of the live channel statistics. Basically they want to know two things:

  • The maximum number of children watching the live channel simultaneously;
  • The average number of children online, during the show, which starts at the beginning of second 1 and ends at the end of second $m$.

输入格式

The first line contains two space-separated integers $n$ and $m$ ($1 \le n \le 250~000$, $1 \le m \le 10^9$), denoting the number of children log-in record, the length of the show.

The next $n$ line each contains two space-separated integers $s_i$ and $t_i$ ($1 \le s_i \le t_i \le m$), meaning that a child starts to watch the channel at the start of second $s_i$, and leave the channel at the end of second $t_i$. Notice that the same pair of $(s,t)$ might appear multiple times, they are believed to be different records.

You can safely assume that these records all belong to different children.

输出格式

In the first line, output the maximum number. You can write it as an integer, or a floating number, as you like.

In the second line, output the average number as a floating number.

The absolute or relative error should be not greater than $10^{-12}$.

样例

Input
2 10
1 5
5 10
Output
2
1.1
Input
4 10
1 3
4 4
8 8
5 7
Output
1
8E-1
Input
5 10
5 6
4 7
3 8
2 9
1 10
Output
5.000000000000000
3

121 人解决,159 人已尝试。

144 份提交通过,共有 849 份提交。

3.7 EMB 奖励。

创建: 6 年,2 月前.

修改: 6 年,1 月前.

最后提交: 3 年,10 月前.

来源: EOJ Monthly 2018.8

题目标签