422. Fast Typing

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Vasya has little experience in typing, thus he has to look at the keyboard to locate the necessary keys, and still makes typos while doing so. For simplicity sake, we'll assume that the only type of typo he makes is replacing a character by another one. To correct those, he employs the following strategy: from time to time, he looks at the screen, and if there is any typo in the text, he removes all the characters from the end of the text to the first typo he made inclusive (i.e., he leaves only the correct part of the text intact) by pressing 'backspace' key several times, and continues typing from that position again.

Pressing any key (including 'backspace') takes 1 unit of time, and looking at the screen takes t units of time. Given the probabilities of making an error for each character in the text, compute the minimal possible expected time to type the entire text correctly (including verifying that by looking at the screen in the end and noticing no typos).

The text is n characters long, and the probability of mistyping i-th character is equal to ai.

The input file contains two integer numbers n and t (1 ≤ n ≤ 3000, 1 ≤ t ≤ 106), followed by n real numbers ai ().

Output one real number — the minimal possible expected time. Your answer will be considered correct if it is within 10-6 relative error of the exact answer.

sample input
sample output
3 1
0.00001 0.5 0.00001

Online Contester Team © 2002 - 2010. All rights reserved.