Марыся сдает экзамен, состоящий из $n$ вопросов. Ответ на каждый вопрос оценивается следующим образом:
- 1 балл за правильный ответ,
- 0 баллов за отсутствие ответа,
- −1 балл за неправильный ответ.
Чтобы сдать экзамен, нужно набрать не менее $t$ баллов.
Для каждого вопроса Марыся подготовила потенциальный ответ, но она не всегда уверена в его правильности. Точнее, для $i$-го вопроса она знает, что ответ правильный с вероятностью $p_i$. Правильность ответов на разные вопросы — независимые события.
Марыся должна выбрать, на какие вопросы ответить, а какие оставить без ответа, чтобы максимизировать вероятность сдачи экзамена.
Входные данные
В первой строке входных данных находятся два целых числа $n, t$ ($1 \le t \le n \le 50\,000$): количество вопросов и минимально необходимое количество баллов.
В следующих $n$ строках находятся вероятности правильности ответов: $i$-я из этих строк содержит вещественное число $p_i$ ($0 \le p_i \le 1$), которое имеет не более 9 знаков после десятичной точки.
Выходные данные
В единственной строке выходных данных должно содержаться одно вещественное число: вероятность того, что Марыся сдаст экзамен, если она оптимально выберет, на какие вопросы отвечать. Число должно быть записано в десятичном виде (не в экспоненциальном) с не более чем 20 знаками после запятой.
Максимально допустимая абсолютная погрешность составляет $10^{-6}$.
Примеры
Пример 1
5 2 0.77 0.85 0.75 0.98 0.6
0.8798125
Пример 2
5 3 0.3 0.01 0.2 0.15 0
0.009
Пример 3
3 3 0.000001 0.000001 0.000001
0
Примечание
В первом примере оптимальная стратегия — ответить на первые 4 вопроса, а последний оставить без ответа. Таким образом, даже при одном неправильном ответе Марыся получит 2 балла.
Во втором примере оптимальная стратегия — ответить на первый, третий и четвертый вопросы. Марыся получит 3 балла, если все эти ответы будут правильными. Поскольку эти события независимы, вероятность составляет $0,3 \cdot 0,2 \cdot 0,15 = 0,009$.
В последнем примере вероятность успеха равна $10^{-18}$, мы можем округлить её до 0.