Нещодавно Вася придбав собі захоплюючу гру "Герой Гітари", у котрій всім бажаючим пропонується випробувати себе у ролі рок-гітариста. Для того, щоб пройти її, потрібно щосекунди натискати певні комбінації кнопок (яких, на щастя, небагато). Якщо натиснено потрібні кнопки, то вважається, що гравець зіграв потрібну ноту. У цьому випадку йому нараховується визначена кількість балів (для кожної ноти різна, причому за деякі ноти бали знімаються). Інакше роздається неприємний звук, і ніяких балів не нараховується.

На першому та другому рівні складності Вася все зіграв легко. Проте, перейшовши до третього рівня, він зіткнувся з тим, що не може виконати одну особливо замудру композицію. Після декількох невдалих спроб, Вася раптом помітив, що може правильно зіграти будь-який набір із k або менше нот незалежно від їхньої складності. З іншого боку, йому ніяк не вдається правильно озвучити k + 1 ноту підряд, навіть якщо вона і нескладна. Оскільки Вася не психолог, він не спромігся пояснити, чому так відбувається. Але після недовгих пошуків у інтернеті він знайшов докладний опис того, скільки балів нараховується за кожну правильно зіграну ноту. Користуючи цим, він хоче визначити, яку максимальну кількість балів він може набрати. Допоможіть Васі.

Вхідні дані

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

Вихідні дані

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