Many of us know the sad story about the stairs where the robbers sat. However, times are changing, and robbers have introduced a discount system to lure the customers. Now the robbers on one of the steps after they rob, issue a card with a discount of 50%. The holder of this card pays the robbers on the steps 2 times less!
For the rest the rules of moving up the stairs left the same - you start to climb from the floor (from the zero step), and you can jump any number of steps from 1 to k. At each step there are robbers who will force you to pay c[i]
rubbles if you get to their step. You must get to the stair number n, paying as little money as possible.
First line contains the number of stairs n (n ≤ 10^5
) and the length of the maximum possible jump k (1 ≤ k ≤ 100). Во второй строке содержится n чисел c[i]
- количество денег, которое нужно заплатить грабителям на i-той ступеньке (с 1 по n-ную) в рублях. Поскольку бандитам не хочется возиться с мелочью, все c[i]
(0 ≤ c[i]
≤ 10^4
) четные. В третьей строке одно число d (1 ≤ d ≤ n) - номер ступеньки, на которой грабители дают дисконтную карту.
Выведите искомое число - минимальную цену прохождения лестницы в рублях.