Алгоритмы — мальчик на лестнице: шаг, прыжок и k телепортов

Условие

Мальчик подошёл к лестнице из n ступенек. С каждой ступенькой связано число a_i (|a_i| ≤ 100) — изменение настроения, если ступить на неё. Мальчик умеет:

• шагнуть на следующую ступеньку,
• перепрыгнуть через одну,
• абстрагироваться от воспоминаний и пройти вперёд на любое количество ступенек, не меняя настроения. Эту опцию можно использовать не более k раз.

Изначально мальчик стоит перед первой ступенькой. Ему нужно оказаться на последней.

Какое максимальное настроение он может получить?

1 ≤ n ≤ 1000, 0 ≤ k ≤ 100.