eolymp
bolt
Try our new interface for solving problems
Məsələlər

Герой гитары

Герой гитары

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Недавно Вася приобрел себе увлекательную игру "Герой Гитары", в которой всем желающим предлагается опробовать себя в роли рок-гитариста. Для того, чтобы пройти ее, нужно каждую секунду зажимать определенные комбинации кнопок (которых, к счастью, немного). Если зажаты нужные кнопки, то считается, что игрок сыграл нужную ноту. В этом случае ему начисляется определенное количество очков (для каждой ноты разное, причем за некоторые ноты очки снимаются). Иначе раздается неприятный звук, и никаких очков не начисляется.

На первом и втором уровне сложности Вася все играл легко. Однако, перейдя на третий уровень, он столкнулся с тем, что не может исполнить одну особенно замысловатую композицию. После нескольких неудачных попыток, Вася неожиданно заметил, что может правильно сыграть любой отрезок из k или менее нот вне зависимости от их сложности. С другой стороны, ему никак не удается правильно исполнить k + 1 ноту подряд, даже если они очень простые. Поскольку Вася не психолог, он не смог понять, почему так происходит. Зато после недолгих поисков в интернете он нашел подробное описание того, сколько очков начисляют за каждую правильно сыгранную ноту. Пользуясь этим, он хочет определить, какое максимальное количество очков он может набрать. Помогите Васе.

Giriş verilənləri

В первой строке содержатся два целых числа n и k (1n10000, 1k1000), где n - количество нот в композиции. Во второй строке n целых чисел - количество очков, получаемых за сыгранные ноты. Все числа по модулю не превышают 10^9.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
5 2
2 3 1 4 5
Çıxış verilənləri #1
14
Giriş verilənləri #2
5 1
2 3 1 4 5
Çıxış verilənləri #2
8
Giriş verilənləri #3
5 2
2 3 1 -4 5
Çıxış verilənləri #3
10
Mənbə 2009 Цикл интернет-олимпиад для школьников. Седьмая индивидуальная олимпиада, 10 января, Задача A