题目描述

可莉对 "玩 "的定义是把炸药扔得到处都是；她特别喜欢 "炸鱼"--在满是鱼的湖里扔炸弹。今天，可莉还打算在星落湖里炸鱼。

可莉将使用威力为$x$的炸弹，然后，每条$HP$小于或等于$x$的鱼都会被炸死。

然而，可莉并不知道每条鱼的$HP$。

相反，她只知道第$i$条鱼的$HP$是$[l_i, r_i]$中的一个均匀随机的实数。

现在，可莉想确定最小可能的$x$，使预期的被炸鱼的数量大于或等于$m$。

输入格式

第一行包含两个整数$n$，$m$----鱼的数量和可莉对被炸死的鱼的数量的预期。

在下面的$n$行中，每行包含两个实数$l_i$, $r_i$-----这意味着第$i$条鱼的$HP$将是$[l_i, r_i]$中的一个随机实数。

输出格式

输出最小可能的$x$，使得预期的炸鱼数量大于或等于$m$。

样例

样例输入1

2 1
1.4 2.8
1.4 2.8

样例输出1

2.1000000000

样例输入2

3 2
1.5 3.0
2.4 5.0
1.919810 1.919810

样例输出2

2.7804878048

样例输入3

1 1
0 1000000000

样例输出3

1000000000.0000000000

数据范围与提示

在样例$1$中，如果可莉扔了一颗威力为 $2.1$ 的炸弹，炸死鱼 $1$ 的概率为 $0.5$，炸死鱼 $2$ 的概率为 $0.5$，因此炸死鱼数量的预期为 $0.5+0.5=1$。

$1 \leq m \leq n \leq 10_5$

$0 \leq l_i \leq r_i \leq 10_9$

注意：

这道题为$special judge$----如果你的答案和实际答案绝对值差$\leq 10^{-4}$将会被判为$Accepted$