Problem G
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 $n$ yes/no questions. Answering correctly gives $+1$ point, answering incorrectly gives $-1$ point, and not answering gives $0$ points. To pass the exam, at least $k$ points are needed. For each question, Gustav has a guess that he knows is correct with probability $p_ i$ ($0.5 \leq p_ i \leq 1$). Note that $p_ i \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.
Input
The first line contains the two integers $n$ and $k$ ($1 \leq k \leq n \leq 5000$). The second line contains $n$ real numbers $p_ i$ ($0.5 \leq p_ i \leq 1.0$). These numbers will have at most $6$ digits after the decimal point.
Output
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}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 0.5 0.5 0.5 |
0.125 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 0.9 0.5 0.9 0.9 |
0.972 |
