Герой гитары
Герой гитары
Недавно Вася приобрел себе увлекательную игру "Герой Гитары", в которой всем желающим предлагается опробовать себя в роли рок-гитариста. Для того, чтобы пройти ее, нужно каждую секунду зажимать определенные комбинации кнопок (которых, к счастью, немного). Если зажаты нужные кнопки, то считается, что игрок сыграл нужную ноту. В этом случае ему начисляется определенное количество очков (для каждой ноты разное, причем за некоторые ноты очки снимаются). Иначе раздается неприятный звук, и никаких очков не начисляется.
На первом и втором уровне сложности Вася все играл легко. Однако, перейдя на третий уровень, он столкнулся с тем, что не может исполнить одну особенно замысловатую композицию. После нескольких неудачных попыток, Вася неожиданно заметил, что может правильно сыграть любой отрезок из k или менее нот вне зависимости от их сложности. С другой стороны, ему никак не удается правильно исполнить k + 1 ноту подряд, даже если они очень простые. Поскольку Вася не психолог, он не смог понять, почему так происходит. Зато после недолгих поисков в интернете он нашел подробное описание того, сколько очков начисляют за каждую правильно сыгранную ноту. Пользуясь этим, он хочет определить, какое максимальное количество очков он может набрать. Помогите Васе.
Giriş verilənləri
В первой строке содержатся два целых числа n и k (1 ≤ n ≤ 10000, 1 ≤ k ≤ 1000), где n - количество нот в композиции. Во второй строке n целых чисел - количество очков, получаемых за сыгранные ноты. Все числа по модулю не превышают 10^9
.
Çıxış verilənləri
Выведите одно число - максимальное число очков, которое может получить Вася.
Nümunə
5 2 2 3 1 4 5
14
5 1 2 3 1 4 5
8
5 2 2 3 1 -4 5
10