题目描述

Ashley 和 Brandon 正在设计一个生存游戏。游戏分若干回合，每个回合由白天和夜晚组成。

有 $k$ 名玩家需要在野外生存很多回合：

• 白天可以采集食物；
• 夜晚每个玩家都必须吃到固定数量的食物，否则会饿死；
• 第 $i$ 天采集到的食物最多为 $q_i$；
• 这些食物必须在某个未来夜晚之前吃掉，超过保质期就不能再吃。

具体地，第 $i$ 天采集到的食物在第 $f_i$ 个夜晚之后变质，因此只能用于第 $i,i+1,\ldots,f_i$ 个夜晚。

设计者现在需要选择一个正数 $x$，表示每个玩家每晚都要吃 $x$ 单位食物。问最大的可行 $x$ 是多少。如果不存在任何正数 $x$ 能让所有玩家活下来，输出 -1。

输入格式

第一行包含两个整数 $n,k$：

• $1 \le n \le 10^6$，表示回合数；
• $1 \le k \le 39$，表示玩家数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $q_i,f_i$：

• $0 \le q_i \le 10^9$；
• $i \le f_i \le n$；
• $q_i$ 表示第 $i$ 天最多能采集的食物量；
• $f_i$ 表示这些食物在第 $f_i$ 个夜晚之后变质。

输出格式

输出一个实数，表示每个玩家每晚能吃的最大正数食物量。

如果对任意正数都不可行，输出：

-1

答案允许绝对误差或相对误差不超过 $10^{-9}$。

样例 #1

输入

2 1
4 2
3 2

输出

3.5

样例 #2

输入

2 2
4 1
3 2

输出

1.5

样例 #3

输入

1 17
0 1

输出

-1