在房地产市场进行投机是一项压力巨大且收益不稳定的工作。如果你能从父母那里得到一大笔贷款，并且能够精确预测某些特定日期的公寓价格，这会有所帮助吗？

你开始时没有公寓，但你的银行账户余额为 $10^{100}$。由于你没有房地产经纪人执照，你一次最多只能拥有一套公寓。你已经看中了一套地理位置优越的特定公寓，这就是你可以购买并随后卖出的公寓，可能会进行多次买卖。

行业门户网站 MyHouse 发布了未来 $n$ 天内该公寓价格的预测区间 $[a_i, b_i]$（其中 $a_i < b_i$）。第 $i$ 天的公寓价格是一个在区间 $[a_i, b_i]$ 内均匀随机生成的实数 $c_i$。默认情况下，你会在第 $i$ 天开始时得知价格 $c_i$。然后你必须决定是否进行交易。如果你拥有该公寓，你可以以 $c_i$ 的价格卖出它；如果你未拥有该公寓，你可以以 $c_i$ 的价格买入它。

只有在今天（第一天之前），MyHouse 门户网站允许新用户获取所选的 $k$ 天的精确价格 $c_i$。也就是说，你现在可以选择一个包含 $k$ 天的集合并得知它们的价格，而对于剩下的 $n - k$ 天中的每一天，你将在该天开始时得知其价格。

在 $n$ 天后，你结束时必须不持有公寓；你的利润是你的最终银行余额与初始银行余额之差。如果你最优地选择这 $k$ 天的集合，并在 $n$ 天中的每一天都做出最优的交易决策，请确定利润的最大期望值*。

* 期望值是随机变量以概率为权重的平均值。直观地说，它是多次重复随机实验时你期望得到的平均结果。

输入格式

第一行包含两个整数 $n$ 和 $k$（$0 \le k \le n \le 300\,000$；$1 \le n$），分别表示天数和你可以立即获知的价格数量。

接下来的 $n$ 行描述价格区间；第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le 10^6$）。

输出格式

输出一个实数——$n$ 天后利润的最大可能期望值。

可接受的相对或绝对误差为 $10^{-6}$。也就是说，如果你输出的答案是 $x$，而正确的精确结果是 $y$，则必须满足 $|x - y| \le 10^{-6} \cdot \max(1, y)$。你最多可以输出小数点后 20 位数字。

样例

输入样例 1

4 0
10 30
10 30
40 50
30 60

输出样例 1

28.75

输入样例 2

4 1
10 30
10 30
40 50
30 60

输出样例 2

31.3888888889

输入样例 3

6 3
10 50
30 70
50 70
30 50
30 40
10 40

输出样例 3

33.6805555556

说明

在第一个样例中，我们有 $k = 0$，因此每个价格都是在当天开始时获知的。存在一种最优策略：在第 1 天或第 2 天以 $17.5$ 的期望成本买入公寓，然后在第 3 天或第 4 天以 $46.25$ 的期望收益卖出。期望利润为 $46.25 - 17.5 = 28.75$。

在第二个样例中，我们有 $k = 1$，我们应该最优地选择第 4 天，这样我们就能立即得知区间 $[30, 60]$ 中的一个实数 $c_4$。在最优交易决策下，期望利润为 $31 \frac{7}{18}$。

在第三个样例中，选择 $k$ 天集合的最优方案是 $\{2, 3, 6\}$。我们立即得知价格 $c_2$、$c_3$ 和 $c_6$。