Egzamin

Marysia podchodzi do egzaminu składającego się z $n$ pytań. Odpowiedź na każde pytanie oceniana jest następująco:

• $1$ punkt za poprawną odpowiedź,
• $0$ punktów za brak odpowiedzi,
• $-1$ punkt za błędną odpowiedź.

Żeby zdać egzamin, trzeba zdobyć co najmniej $t$ punktów.

Dla każdego pytania Marysia ustaliła potencjalną odpowiedź, ale nie zawsze jest pewna, czy jest ona poprawna. Dokładniej, dla $i$-tego pytania wie, że odpowiedź jest poprawna z prawdopodobieństwem $p_i$. Poprawność odpowiedzi dla różnych pytań to zdarzenia niezależne.

Marysia musi wybrać, na które pytania udzielić odpowiedzi, a które zostawić bez odpowiedzi, żeby zmaksymalizować prawdopodobieństwo zdania egzaminu.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $n$, $t$ ($1 ≤ t ≤ n ≤ 50\, 000$): liczba pytań i wymagana minimalna liczba punktów.

W kolejnych $n$ wierszach znajdują się prawdopodobieństwa poprawności odpowiedzi: $i$-ty z tych wierszy zawiera liczbę rzeczywistą $p_i$ ($0 ≤ p_i ≤ 1$), która ma co najwyżej $9$ cyfr po kropce dziesiętnej.

W jedynym wierszu wyjścia powinna znaleźć się jedna liczba rzeczywista: prawdopodobieństwo, że Marysia zda egzamin, jeśli optymalnie wybierze, na które pytania udzielić odpowiedzi. Liczba musi być wypisana w postaci dziesiętnej (nie wykładniczej) z co najwyżej $20$ miejscami po przecinku.

Maksymalny dopuszczalny błąd bezwzględny to $10^{-6}$.

Wyjaśnienie przykładów: W pierwszym przykładzie optymalną strategią jest odpowiedzieć na pierwsze $4$ pytania, a ostatnie zostawić bez odpowiedzi. W ten sposób nawet przy jednej błędnej odpowiedzi Marysia uzyska $2$ punkty.

W drugim przykładzie optymalną strategią jest odpowiedzieć na pierwsze, trzecie i czwarte pytanie. Marysia uzyska $3$ punkty, jeśli wszystkie te odpowiedzi będą poprawne. Ponieważ te zdarzenia są niezależne, prawdopodobieństwo wynosi $0,3 \cdot 0,2 \cdot 0,15 = 0,009$.

W ostatnim przykładzie prawdopodobieństwo sukcesu to $10^{-18}$, możemy je zaokrąglić do $0$.