e-olymp
Задачи

Лесенка

Лесенка

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

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

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

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

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

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

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