题目描述

Cat Noku 有 tickets 张游戏厅奖券，准备把它们投入若干台自动售货机换取奖品。

共有 $n$ 台机器。第 $i$ 台机器有幸运参数 $L_i$ 和奖品价值 $V_i$。每台机器初始都处于刚刚重置的状态。向一台机器投入一张奖券时，设 $K$ 为这台机器自上一次吐出奖品以来收到的奖券数（本次也计入；若今天还没有吐过奖品，则从今天第一次投入开始计数）。本次得到奖品的概率为

$\displaystyle \frac{\min(K^2,L_i^2)}{L_i^2}$。

若成功，则得到一个价值为 $V_i$ 的奖品，同时这台机器的计数重新开始；若失败，则什么也得不到。

Noku 有两个行为限制：

1. 一旦选择了一台机器，他就会不断向这台机器投入奖券，直到得到奖品，或者奖券全部用完；
2. 每次得到奖品后，下一次必须选择另一台机器。也就是说，连续两个奖品不能来自同一台机器。

在所有满足这些规则的策略中，求最终得到的奖品总价值的最大期望。

输入格式

第一行包含两个整数 $n$ 和 tickets。

接下来 $n$ 行，第 $i$ 行包含两个整数 $L_i,V_i$。

输出格式

输出一个实数，表示最大期望价值。

若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-4}$，则视为正确。

数据范围

• $1\le \text{tickets}\le 40000$；
• $2\le n\le 15$；
• $1\le L_i,V_i\le 10^9$。

样例

输入

2 4
2 4
3 5

输出

7.693072702331962