Вы играете в игру с мешком с красными и черными шарами. Изначально вам сказали, что всего в мешке n шаров. Кроме того, вам сказали, что есть вероятность pi / 106 того, что мешок содержит ровно i красных шаров.
Теперь вы хотите купить шары из этого мешка. Вам очень нравится красный, поэтому красный шар для вас имеет ценность 1, а черные имеют нулевую ценность. Чтобы купить шар, если в мешке все еще есть шары, вы платите цену c, где 0 ≤ c ≤ 1, и вытаскиваете случайный шар из мешка. Вы можете закончить игру в любой момент (и даже можете ничего не покупать совсем).
Вы хотите покупать оптимально так, чтобы максимизировать математическое ожидание выигрыша (т.е. количества красных шаров минус стоимость всех покупок). Выведите максимально возможное математическое ожидание выигрыша.
Первая строка содержит два целых числа n, X (1 ≤ n ≤ 10 000, 0 ≤ X ≤ 106).
Вторая строка содержит n + 1 целое число p0, p1, ... pn (0 ≤ pi ≤ 106, 
).
Величина c может быть вычислена как
.
Выведите одно вещественное число, равное искомому максимальному математическому ожиданию выигрыша.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит 10 - 9. А именно, если ваш ответ равен a, а ответ жюри равен b, ваш ответ будет засчитан, если 
.
3 200000
250000 250000 250000 250000
0.9000000000
В данном примере равновероятны варианты, что в мешке 0,1,2,3 красных шаров. Стоимость взятья одного шара равна 0.2.
