Работа в команде
На его любимый праздник Фермер Джон хочет послать подарки своим друзьям. ФД позвал коров на помощь в заворачивании подарков.
n коров ФД стоят в ряд, последовательно пронумерованные 1..n. Корова i имеет s[i] - уровень мастерства в заворачивании подарков. ФД решил объединить коров в команды. Команда состоит из любого последовательного множества коров числом не более k коров, и корова не может быть более чем в одной команде. Поскольку коровы могут учиться друг у друга, уровень мастерства каждой коровы в команде может быть заменен на уровень мастерства самой мастеровитой коровы.
Помогите ФД определить максимально возможную сумму уровней мастерства, которую он может получить, оптимально сформировав команды.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 10^4) и k (1 ≤ k ≤ 1000). Следующие n строк содержат уровни мастерства n коров в порядке как они стоят. Каждый уровень мастерства это положительное целое число не более 10^5.
Выходные данные
Выведите наибольшую возможную сумму уровней мастерства, которую может получить ФД, сгруппировав коров по командам.
Пример
В этом примере оптимальное решение - сгруппировать первые 3 коровы и последние 3 коровы, оставив среднюю корову саму оп себе. Напомним, что можно иметь команды размером меньше чем k. Уровни мастерства вырастут до 15, 15, 15, 9, 10, 10, 10, что и даёт сумму 84.