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$ 的条件限制。

附件

file

数据范围与提示

「样例解释 #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$。

捆绑包编号	$n \leq$	$m$	分值
$1$	$10$	$= 3$	$5$
$2$	$10^5$	$= 0$
$3$	$100$	$< n$	$10$
$4$	$2 \times 10^3$	$= 1$	$15$
$5$	$10^5$
$6$		$< n$	$50$