You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

A.分身(avatar)

题目描述

青蛙和周欣准备参加下一次的 NOB(National Olympiad in Badminton)。

青蛙想要在一场比赛中击回对手打出的所有球从而赢得比赛，因为青蛙非常强，所以他会影分身之术，他总共可以召唤出 $m$ 个影分身，所以场上总共可以有 $m+1$ 个人。

由于周欣打球太菜，所以他并不会上场，但是他可以预先知道对手打出的每一个球的位置，他想要计算一下最优策略下青蛙想要打败对手需要多认真。

形式化的，我们将羽毛球场比作一个一维数轴，不考虑高度的限制。起初所有影分身都在 $0$ 点上，每个影分身的移动是独立的，并且可以互相越过或处于同一位置。任意时刻，他们可以以不超过 $V$ 的速度移动或处于静止状态。

现在预测到了对手将能打出 $n$ 次球，第 $i$ 个球将于时刻 $t_i$ 飞到位置 $x_i$，也就是说在时刻 $t_i$ 青蛙的本体或者他的一个影分身必须位于 $x_i$ 才能击回第 $i$ 个球。现在请你求出青蛙若想击回所有的球，速度上限 $V$ 至少是多少。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行两个整数 $t$ 和 $x$，含义同题目描述。

输出格式

输出青蛙和他的分身击回所有球的速度上限 $V$ 的最小值，你的答案和标准答案的相对误差或绝对误差在 $10^{-3}$ 以内将视为答案正确。

样例输入 #1

4 1
1 2
2 4
5 0
6 4

样例输出 #1

2.000000

样例输入 #2

3 0
4 -7
5 10
6 3

样例输出 #2

17.000000

样例输入 #3

5 3
3 8
4 -5
6 6
8 0
10 -6

样例输出 #3

2.666660

样例输入 #4

5 2
1 10
5 -5
6 9
7 -1
10 -10

样例输出 #4

9.999994

「样例 #5」

见题目附件下的 ex_avatar/avatar0_05.in 与 ex_avatar/avater0_05。

该样例满足捆绑包 $3$ 的条件限制。

「样例 #6」

见题目附件下的 ex_avatar/avatar0_06.in 与 ex_avatar/avater0_06。

该样例满足捆绑包 $4$ 的条件限制。

「样例 #7」

见题目附件下的 ex_avatar/avatar0_07.in 与 ex_avatar/avater0_07。

该样例满足捆绑包 $5$ 的条件限制。

「样例 #8」

见题目附件下的 ex_avatar/avatar0_08.in 与 ex_avatar/avater0_08。

该样例满足捆绑包 $6$ 的条件限制。

数据范围与提示

「样例解释 #1」

场上共有 $2$ 个人，一个人接第 $1,2,4$ 个球，一个人待在原地接第 $3$ 个球。

「样例解释 #2」

场上只有一个人，速度的上界在接第 $1,2$ 个球之间产生。

「数据范围」

本题采用捆绑测试。

对于全部数据，$0 \leq m < n \leq 10^5$，$1 \leq t \leq 10^9$，$- 10^6 \leq x \leq 10^6$。

对于任意的 $i < j$，保证 $t_i < t_j$。

大样例