Грабители с большой лестницы
Многим из нас известна печальная история про лестницу, на которой засели грабители. Однако времена меняются, и грабители, чтобы завлечь клиентов, ввели дисконтную систему. Теперь грабители на одной из ступеней после того, как ограбят, выдают карточку со скидкой 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) - номер ступеньки, на которой грабители дают дисконтную карту.
Выходные данные
Выведите искомое число - минимальную цену прохождения лестницы в рублях.