Graduation Guarantee

문제

Gustav is studying to become an interpreter. In this line of work, knowing several languages is a must, and Gustav is already fluent in French, Mandarin, Nahuatl and even Finnish. But there is one language that Gustav struggles with: Norwegian. Before Gustav can graduate, he must complete the infamous Norwegian Conclusive Proficiency Check.

This exam consists of $nn$ yes/no questions. Answering correctly gives $+1+1$ point, answering incorrectly gives $-1-1$ point, and not answering gives $00$ points. To pass the exam, at least $kk$ points are needed. For each question, Gustav has a guess that he knows is correct with probability $p_{i}p\_i$ ($0.5\le p_i\le 10.5\; \backslash leq\; p\_i\; \backslash leq\; 1$). Note that $p_i\ge 0.5p\_i\; \backslash geq\; 0.5$, because otherwise guessing the opposite would be better.

What is the maximum possible probability of passing the exam, assuming we carefully choose which questions to answer and which ones to leave unanswered? Note that unlike a programming contest, the exam does not have instant feedback. So Gustav will answer the questions, hand in his answers, and only later be told the results.

입력

The first line contains the two integers $nn$ and $kk$ ($1\le k\le n\le 50001\; \backslash leq\; k\; \backslash leq\; n\; \backslash leq\; 5000$). The second line contains $nn$ real numbers $p_{i}p\_i$ ($0.5\le p_i\le 1.00.5\; \backslash leq\; p\_i\; \backslash leq\; 1.0$). These numbers will have at most $66$ digits after the decimal point.

출력

Output the probability that we pass the exam. Your answer will be considered correct if it has an absolute or relative error of at most ${10}^{-6}10^\{-6\}$.