Герой гітари#608
Василь нещодавно придбав захопливу гру під назвою "Guitar Hero". У цій грі гравці можуть спробувати себе у ролі рок-гітариста. Щоб пройти гру, необхідно щосекунди натискати певні комбінації кнопок. На щастя, цих комбінацій не так вже й багато. Якщо потрібні кнопки натиснуто, гравець правильно виконує ноту та отримує певну кількість балів (кількість балів для кожної ноти може бути різною, а для деяких навіть від'ємною). В іншому випадку лунає неприємний звук і бали не нараховуються.
Василь легко пройшов перший і другий рівні складності. Проте, дійшовши до третього рівня, він зіткнувся з особливо складною композицією, яку не зміг виконати. Після кількох невдалих спроб Василь зрозумів, що може правильно зіграти будь-який відрізок із або менше нот незалежно від їхньої складності. Проте він не може правильно зіграти k + 1 нот підряд, навіть якщо вони дуже прості. Чому так відбувається, він сам пояснити не може. Однак після швидкого пошуку в інтернеті він знайшов детальну інформацію про кількість балів, які нараховуються за кожну ноту у разі її правильного виконання. Користуючись цією інформацією, Василь хоче визначити максимальну кількість балів, яку він може набрати. Допоможіть Василю.
У першому рядку містяться два цілі числа та (1 \le n \le 10000, 1 \le k \le 1000), де — кількість нот у композиції. У другому рядку розташовано цілих чисел, що означають кількість балів за кожну ноту у разі її правильного виконання. Абсолютне значення кожного числа не перевищує 10^9.
Виведіть одне число — максимальну загальну кількість балів, яку може набрати Василь.
Приклад 1
Приклад 2
Приклад 3