Ashley 和 Brandon 正在设计一款名为“Don’t Hunger Together”的生存电子游戏。游戏规则如下：

游戏按回合进行。每一回合包含一个白天和一个夜晚。几名玩家必须在荒野中生存多个回合。他们在白天收集食物，并在夜晚进食。在白天，他们最多可以搜寻到一定数量的食物，且当天找到的食物必须在未来的某个夜晚之前吃掉。任何剩余的此类食物都会变质且无法食用。每天晚上，每位玩家必须吃掉一定数量的食物，否则他们会饿死。如果每位玩家在每个夜晚都能吃到足够的食物，他们就赢了。

Ashley 和 Brandon 已经设计好了一个场景，他们最后需要做的是确定每位玩家每天晚上必须吃的食物数量。他们希望知道这个数量的最大可能值，该值必须为正数。然而，如果游戏在任何正数值下都无法获胜，请告知 Ashley 和 Brandon 该场景是不可能完成的！

输入格式

输入的第一行包含两个整数 $n$ ($1 \le n \le 10^6$) 和 $k$ ($1 \le k \le 39$)，其中 $n$ 是游戏的回合数，$k$ 是玩家人数。回合编号从 $1$ 到 $n$。

接下来的 $n$ 行，每行包含两个整数 $q$ ($0 \le q \le 10^9$) 和 $f$ ($i \le f \le n$)，其中 $q$ 是该回合白天可以搜寻到的食物数量，$f$ 是该食物变质前的未来回合的夜晚编号，其中 $i$ 是当前回合编号。回合按 $1$ 到 $n$ 的顺序排列。

输出格式

输出一个实数，表示每位玩家在每个夜晚可以吃掉并仍能存活下来的最大正食物数量；如果该情况在任何正数值下都无法获胜，则输出 $-1$。任何与标准答案的绝对误差或相对误差在 $10^{-9}$ 以内的答案都将被接受。

样例

样例输入 1

2 1
4 2
3 2

样例输出 1

3.5

样例输入 2

2 2
4 1
3 2

样例输出 2

1.5

样例输入 3

1 17
0 1

样例输出 3

-1