e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Лесенка

Лесенка

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

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
3
1 -1 1
2
Выходные данные #1
2