题目描述

Vasya 打字时必须低头看键盘，因此仍可能输错字符。我们只考虑一种错误：本应输入某个字符，却输入了另一个字符。

为了纠错，他会不时查看屏幕。如果发现至少一个错误，就不断按退格键，从当前文本末尾一直删除到第一次输错的字符（包含该字符），只保留此前完全正确的前缀，然后从那里继续输入。

按任意一个键（包括退格键）耗时 $1$，查看一次屏幕耗时 $t$。第 $i$ 个字符每次输入错误的概率为 $a_i$，各次输入相互独立。

你可以决定在什么时候查看屏幕。求最终完整、正确地输入全部 $n$ 个字符，并在最后查看屏幕确认无误所需时间的最小期望值。

输入格式

第一行两个整数 $n,t$。

第二行包含 $n$ 个实数 $a_1,a_2,\ldots,a_n$。

限制：

• $1\le n\le 3000$；
• $1\le t\le 10^6$；
• $10^{-5}\le a_i\le \frac12$。

输出格式

输出最小期望时间。

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

样例

3 1
0.00001 0.5 0.00001

8.000080000800008

限制

• 时间限制：0.25 秒
• 空间限制：256 MB