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

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

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

В первой строке дано число n, не превосходящее 105 - количество ступеней и число k от 1 до 100 - верхний диапазон дальности прыжка. Во второй строке содержится n чисел ci - количество денег, которое нужно заплатить грабителям на i-той ступеньке (с 1 по n-ную) в рублях. Поскольку бандитам не хочется возиться с мелочью, все ci (0 ≤ ci ≤ 104) четные. В третьей строке одно число d (1 ≤ d ≤ n) - номер ступеньки, на которой грабители дают дисконтную карту.

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

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