有 $$$n + 1$$$ 个城市,编号从 $$$0$$$ 到 $$$n$$$,由 $$$n$$$ 道路连接。第 $$$i$$$-th $$$(1 \leq i \leq n)$$$ 路双向连接城市 $$$i-1$$$ 和城市 $$$i$$$。当水母飞回城市$$$0$$$后,她发现她把Miku fufu落在了城市$$$n$$$。
每条路都有一个正整数的美丽程度。将第$$$i$$$条路的美丽表示为$$$a_i$$$。
水母正在寻找她的福福。由于方向感很差,她不知道该走哪条路。每天,她都会随机选择一条与她当前所在城市相连的道路并穿过它。令 $$$s$$$ 为连接当前城市的道路美景的总和。对于每条连接当前城市的道路,Jellyfish 都会以 $$$\frac x s$$$ 的概率遍历该道路,其中 $$$x$$$ 是道路的美景,到达道路另一边的城市。
Jellyfish将从城市$$$0$$$开始,当她到达城市$$$n$$$时,她只会得到她的fufu。
您想要选择美丽的道路,以使水母找到她的福福所需的预计天数尽可能短。但由于资金有限,所有道路的美女总和必须小于或等于$$$m$$$。
如果选择了最佳的道路美景,求水母恢复她的福福所需的最少预计天数。
输入
输入的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq m \leq 3000$$$) - 道路的数量和道路美丽的最大总和。
输出
输出如果道路的美丽被最佳选择,水母需要得到她的福福的最少预期天数。
如果绝对或相对误差不超过 $$$10^{-9}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$$$,则认为您的答案是正确的。
示例
输入 #1
3 8
输出 #1
5.200000000000
输入 #2
10 98
输出 #2
37.721155173329
注意
在第一个例子中,美丽的最优分配是$$$a=[1, 2, 5]$$$。水母取回她的福福所需的预计天数是 $$$5.2$$$。