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