Robbers from the Grand Staircase#5330
Many of us know the unfortunate tale of the staircase where robbers lie in wait. However, times have changed, and to attract more "customers," the robbers have introduced a discount system. Now, on one of the steps, after robbing you, they offer a discount card that provides a 50% reduction. With this card, you pay the robbers on subsequent steps only half the usual amount!
Apart from this change, the rules for ascending the staircase remain unchanged: you start from the ground floor (step ), and you may jump any number of steps from up to at a time. On each step, robbers demand a payment of c_i rubles if you land there. Your goal is to reach step number while spending as little money as possible.
The first line contains two integers, (1 \leq n \leq 10^5) — the number of steps, and (1 \leq k \leq 100) — the maximum number of steps you can jump at once.
The second line contains integers c_1, c_2, \ldots, c_n (0 \leq c_i \leq 10^4, all even), each representing the cost in rubles to pay the robbers on the -th step.
The third line contains a single integer (1 \leq d \leq n) — the index of the step where the robbers offer the discount card.
Print a single integer — the minimum total cost in rubles required to ascend the staircase.
Example 1