题目描述

Marysia 要参加一场有 $n$ 道题的考试。每道题的评分规则如下：

• 正确回答得 $1$ 分；
• 不回答得 $0$ 分；
• 错误回答得 $-1$ 分。

要通过考试，总分必须达到至少 $t$ 分。对于每道题，Marysia 都准备了一个可能的答案，但她并不总是确定答案是否正确。具体来说，对于第 $i$ 道题，她知道答案正确的概率是 $p_{i}$。每道题的正确性相互独立。

请你帮 Marysia 决定，哪些题该回答，哪些题该留空，以最大化她通过考试的概率。

输入格式

输入的第一行包含两个整数 $n, t$ $(1 \leq t \leq n \leq 50000)$，分别表示题目数量和通过考试所需的最低分数。

接下来的 $n$ 行给出每道题答案正确的概率：第 $i$ 行包含一个实数 $p_{i}$ $(0 \leq p_{i} \leq 1)$，小数点后最多有 $9$ 位。

输出格式

输出一行，包含一个实数，表示 Marysia 在最佳选择下通过考试的概率。结果需以十进制形式（非指数形式）表示，小数点后最多 $20$ 位。最大绝对误差为 $10^{-6}$。

5 2
0.77
0.85
0.75
0.98
0.6

0.8798125

在第一个样例中，最优策略是回答前 $4$ 道题，留下最后一道不答。这样，即使有一个错误答案，Marysia 也能获得 $2$ 分。

5 3
0.3
0.01
0.2
0.15
0

0.009

在第二个样例中，最优策略是回答第 $1,3,4$ 道题。如果这三道题都答对，Marysia 将获得 $3$ 分。由于这些事件的独立性，概率为 $0.3 \cdot 0.2 \cdot 0.15 = 0.009$。

3 3
0.000001
0.000001
0.000001

0

在最后一个样例中，成功的概率为 $10^{-18}$，我们可以将其四舍五入为 $0$。