Грабіжники з великих сходів#5330
Багатьом з нас відома сумна історія про сходи, на яких засіли грабіжники. Проте часи змінюються, і щоб привабити більше «клієнтів», грабіжники ввели дисконтну систему. Тепер на одній зі сходинок, після того як вони вас пограбують, вони видають картку зі знижкою 50%. З цією карткою на наступних сходинках ви платите грабіжникам лише половину звичайної суми!
В іншому правила руху сходами не змінилися: ви починаєте підйом з підлоги (сходинка ) і можете стрибати на будь-яку кількість сходинок від до включно. На кожній сходинці грабіжники вимагають оплату c_i рублів, якщо ви потрапили на цю сходинку. Ваша задача — дістатися до сходинки з номером , витративши якомога менше грошей.
У першому рядку задано два цілих числа: (1 \leq n \leq 10^5) — кількість сходинок, та (1 \leq k \leq 100) — максимальна кількість сходинок, які можна перестрибнути за раз.
У другому рядку задано цілих чисел c_1, c_2, \ldots, c_n (0 \leq c_i \leq 10^4, всі парні) — кількість рублів, яку потрібно заплатити грабіжникам на -й сходинці.
У третьому рядку задано одне ціле число (1 \leq d \leq n) — номер сходинки, на якій грабіжники видають дисконтну карту.
Виведіть одне число — мінімальну суму в рублях, необхідну для проходження сходів.
Приклад 1