На каждой из n + 2 ступенек лестницы записано целое число, причем на первой и на последней ступеньке записано число 0. На первой ступеньке стоит человек, которому необходимо подняться на последнюю ступеньку. За один шаг он может подниматься на любое число ступенек, не превосходящее k.

Подсчитаем сумму всех чисел, написанных на ступеньках, на которые наступил человек. Найдите наибольшее возможное значение этой суммы.

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

В первой строке записано число n (0 ≤ n ≤ 1000). Во второй строке записано n целых чисел записанных на ступеньках и не превосходящих по модулю 1000 (за исключением первой и последней ступеньки, на которых записаны нули). В третьей строке записана максимальная величина шага человека k (1 ≤ k ≤ n).

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

Выведите максимально возможную сумму чисел, записанных на ступеньках, на которые наступил человек.