AT_tenka1_2016_final_f Blind Purchase

天下一玩具店因低价出售手办而闻名。这家店有 $N$ 种手办，我们将其依次编号为手办 $1$、手办 $2$，直到手办 $N$。 在店铺的 $1$ 层，你可以按单价 $P_i$ 日元购买第 $i$ 个手办（一种一个）。 在店铺的 $2$ 层，有一台自动售货机，插入 $G$ 日元后，可以随机获得 $N$ 种手办中的一种，概率均为 $1/N$。因为机器会自动生成手办，所以每种手办获得的概率总是相等的。 你的目标是在这家店中至少收集到每种手办各一个。你可以自由选择在 $1$ 层和 $2$ 层购物的顺序和次数，而且我们不限制你的花费。你的任务是找到一个策略，使得收集到所有手办所需的期望费用最小。这个最小的期望费用是多少？

输入格式如下： > $N$ $G$ $P_1$ $P_2$ ... $P_N$

输出使得收集到所有手办的期望费用最小化的策略下的消费金额期望值。 只要输出的答案绝对误差或相对误差不超过 $10^{-6}$，就被认为是正确的。

- 手办种类数 $2 \le N \le 36$ - 自动售货机费用 $1 \le G \le 36$ - 每种手办单价 $1 \le P_i \le 36$ - 所有输入的数值均为整数。 ### 样例说明 1 有 $2$ 种手办，在 $1$ 层，手办 $1$ 的价格为 $5$ 日元，手办 $2$ 的价格为 $6$ 日元。在 $2$ 层，投 $4$ 日元可随机获得一种手办。最优策略是先用自动售货机买一个手办，再去 $1$ 层购买另一种。如果售货机给出的是手办 $1$，则共花费 $4 + 6 = 10$；如果给出的是手办 $2$，则花费 $4 + 5 = 9$。因此，这种策略下的期望开销为 $1/2 \times 10 + 1/2 \times 9 = 19/2$。任何其他策略都无法使期望费用低于 $19/2$。 ### 样例说明 2 如果自动售货机费用过高，最优策略是在 $1$ 层买下所有手办。 ### 样例说明 3 如果自动售货机价格非常低，最优策略是一直使用它，直到收集齐所有手办品种。 **本翻译由 AI 自动生成**