eolymp
bolt
Try our new interface for solving problems
Problems

Ямы

Ямы

Time limit 2 seconds
Memory limit 64 MiB

У Винни-Пуха большая радость - он купил автомобиль. И теперь, чтобы опробовать покупку, он собрался съездить на нем за медом.

От дома Винни-Пуха до дерева с правильными пчелами, дающими правильный мед, ведет дорога длиной n километров. Казалось бы, скорость передвижения на автомобиле там, где живет Винни, не регламентирована, и ехать можно сколь угодно быстро. Однако, если бы все было так просто, Винни бы не стал обращаться к Вам.

В некоторых местах на дороге расположены ямы. И, если Винни-Пух хочет сохранить свое новое авто в целости и сохранности (а он, конечно же, хочет), проезжать километр, на котором расположена яма, нужно со скоростью, не превышающей k километров в час. Конструкция автомобиля такова, что после каждого проеханного километра он может мгновенно ускориться на один километр в час, замедлиться на эту же скорость или оставить скорость своего движения без изменений. При этом после изменения он будет ровно километр ехать с новой скоростью, после чего снова сможет ее изменить.

Еще одна особенность автомобиля заключается в следующем: он не может мгновенно разогнаться до нужной скорости, зато может мгновенно остановиться (выбросив тормозной парашют). Соответственно, первый километр пути он всегда проедет со скоростью 1 километр в час, а скорость на последнем километре может быть ограничена только наличием на этом километре ям.

Винни любит быструю езду, а еще больше он любит мед. Соответственно, добраться от своего дома до дерева он хочет как можно быстрее. Вас же он попросил определить, за сколько он сможет добраться до дерева и при этом сохранить целым автомобиль.

Input data

В первой строке входного файла даны два целых числа n и k (1n, k1000) - длина дороги и максимальная скорость на участке с ямой, соответственно. В следующей строке дано n чисел, каждое из которых равно 0 или 1 - описание дороги. 0 означает, что соответствующий километр дороги ровный и его можно проезжать с любой скоростью, 1 же, напротив, означает, что километр содержит яму и его можно проехать со скоростью, не превышающей k километров в час.

Output data

Выведите в выходной файл одно вещественное число - минимальное количество часов, за которое Винни-Пух доедет до дерева. Ответ должен отличаться от правильного не больше, чем на 10^{-6}.

Examples

Input example #1
7 1
0 0 1 0 0 0 1
Output example #1
4.833333333
Author Павел Кротков