eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Грабители с большой лестницы

Грабители с большой лестницы

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Многим из нас известна печальная история про лестницу, на которой засели грабители. Однако времена меняются, и грабители, чтобы завлечь клиентов, ввели дисконтную систему. Теперь грабители на одной из ступеней после того, как ограбят, выдают карточку со скидкой 50%. Обладатель такой карточки платит грабителям на ступеньках в 2 раза меньше!

В остальном, правила передвижения по лестнице сохранились - Вы начинаете подъем с пола (т.е. нулевой ступеньки), а прыгать можно на любое количество ступенек от 1 до k. На каждой ступеньке сидят грабители, которые заставят платить c[i] рублей, если вы попадете на их ступеньку. Требуется добраться до ступеньки с номером n, заплатив как можно меньше денег.

Входные данные

В первой строке дано число n, не превосходящее 10^5 - количество ступеней и число k от 1 до 100 - верхний диапазон дальности прыжка. Во второй строке содержится n чисел c[i] - количество денег, которое нужно заплатить грабителям на i-той ступеньке (с 1 по n-ную) в рублях. Поскольку бандитам не хочется возиться с мелочью, все c[i] (0c[i]10^4) четные. В третьей строке одно число d (1dn) - номер ступеньки, на которой грабители дают дисконтную карту.

Выходные данные

Выведите искомое число - минимальную цену прохождения лестницы в рублях.

Пример

Входные данные #1
1 2
0
1
Выходные данные #1
0