Швидкий набір#1930
Вася має невеликий досвід у наборі тексту, тому він часто змушений дивитися на клавіатуру, щоб знайти потрібні клавіші, і все одно робить опечатки. Для простоти будемо вважати, що єдиний тип опечатки, яку він робить — це заміна одного символу іншим. Щоб виправити опечатки, він діє так: час від часу дивиться на екран, і якщо там є опечатка, то видаляє всі символи з кінця тексту до та включно першої помилки (тобто залишається лише правильна частина тексту), натискаючи клавішу 'backspace' кілька разів, і продовжує набирати з цього місця знову.
Натискання будь-якої клавіші (включаючи 'backspace') займає одиницю часу, а погляд на екран забирає одиниць часу. Знаючи ймовірності допущення помилки для кожного символу, обчисліть мінімально можливий очікуваний час набору усього тексту без помилок (включаючи фінальну перевірку з поглядом на екран для переконання, що немає помилок).
Текст містить символів, а ймовірність помилки при введенні -го символу дорівнює a_i.
Вхідний файл містить два цілих числа та (1 \leq n \leq 3000, 1 \leq t \leq 10^6), після яких наведено дійсних чисел a_i (10^{-5} \leq a_i \leq \frac{1}{2}).
Виведіть одне дійсне число — мінімально можливий очікуваний час. Ваша відповідь буде прийнята, якщо відносна похибка не перевищуватиме 10^{-6} від правильної відповіді.
Приклад 1