Fast Typing#1930
Vasya has little experience in typing, so he often has to look at the keyboard to find the necessary keys, and still makes typos. For simplicity, assume that the only kind of typo he makes is replacing one character with another. To correct typos, he uses the following strategy: from time to time, he looks at the screen, and if there is any typo in the text, he removes all characters from the end of the text up to and including the first mistake he made (i.e., leaving only the correct part of the text) by pressing the 'backspace' key several times, and continues typing from that position again.
Pressing any key (including 'backspace') takes unit of time, and looking at the screen takes units of time. Given the probabilities of making a mistake for each character, compute the minimal possible expected time to type the entire text correctly (including a final check by looking at the screen to confirm there are no typos).
The text is characters long, and the probability of mistyping the -th character is a_i.
The input file contains two integers and (1 \leq n \leq 3000, 1 \leq t \leq 10^6), followed by real numbers a_i (10^{-5} \leq a_i \leq \frac{1}{2}).
Output one real number — the minimal possible expected time. Your answer will be accepted if it is within 10^{-6} relative error of the correct answer.
Example 1