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 ci rubbles if you get to their step. You must get to the stair number n, paying as little money as possible.

Input

First line contains the number of stairs n (n ≤ 105) and the length of the maximum possible jump k (1 ≤ k ≤ 100). Во второй строке содержится n чисел ci - количество денег, которое нужно заплатить грабителям на i-той ступеньке (с 1 по n-ную) в рублях. Поскольку бандитам не хочется возиться с мелочью, все ci (0 ≤ ci ≤ 104) четные. В третьей строке одно число d (1 ≤ d ≤ n) - номер ступеньки, на которой грабители дают дисконтную карту.

Output

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