Грабіжники з великих сходів
Многим из нас известна печальная история про лестницу, на которой засели грабители. Однако времена меняются, и грабители, чтобы завлечь клиентов, ввели дисконтную систему. Теперь грабители на одной из ступеней после того, как ограбят, выдают карточку со скидкой 50%. Обладатель такой карточки платит грабителям на ступеньках в 2 раза меньше!
В остальном, правила передвижения по лестнице сохранились - Вы начинаете подъем с пола (т.е. нулевой ступеньки), а прыгать можно на любое количество ступенек от 1 до k. На каждой ступеньке сидят грабители, которые заставят платить c[i] рублей, если вы попадете на их ступеньку. Требуется добраться до ступеньки с номером n, заплатив как можно меньше денег.
Вхідні дані
У першому рядку задано число n, яке не перевищує 10^5 - кількість сходинок та число k від 1 до 100 - верхній діапазон дальності стрибка. У другому рядку міститься n чисел c[i] - кількість грошей, які потрібно заплатити грабіжникам на i-ій сходинці (з 1 по n-ну) в рублях. Оскільки бандити не бажають возитись з дріб'язком, усі c[i] (0 ≤ c[i] ≤ 10^4) парні. У третьому рядку задано одне число d (1 ≤ d ≤ n) - номер сходинки, на якій грабіжники дають дисконтну карту.
Вихідні дані
Виведіть шукане число - мінімальну ціну проходження сходів у рублях.