UOJ Logo

NOI.AC

#8. 小w、小j和小z

统计

小z告诉小w了这样一道送分题。

在数轴上有$n$个小人,第$i$个人现在在$p_i$位置,速度是$v_i$(速度的正负代表不同的方向)。如果某一时刻两个人在同一位置,那么就会发生碰撞。

如果现在小j可以使用能力,使得其中$k$个人凭空消失,那么最多会有多长时间内,没有任何两个人会碰撞呢?

输入格式

一行两个整数 $n$和$k$。

接下来 $n$行,每行两个整数$p_i, v_i$,表示每个人的初始位置和速度。

输出格式

如果时间是无限长,输出Forever, 否则输出一个实数表示答案,答案误差小于$10^{-3}$即可。

样例一

input

4 1 
1 1 
3 -1 
5 2 
7 -2

output

1.00

样例二

input

4 2 
1 1 
3 -1 
5 2 
7 -2

output

Forever

数据范围和约定

本题采用捆绑测试,对于全部数据,$1 \leq k \leq n \leq 10^5; |p_i|, |v_i| \leq 10^9.$

子任务编号 分值 $n$ $k$
110$\leq 20$$\leq n$
220$\leq 200$$\leq 10$
315$\leq n$
415$\leq 2000$$\leq 10$
520$\leq n$
620$\leq 10^5$

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载