На его любимый праздник Фермер Джон хочет послать подарки своим друзьям.
ФД позвал коров на помощь в заворачивании подарков.
\(N\) коров (\(1 \leq N \leq 10^4\)) ФД стоят в ряд, последовательно пронумерованные
\(1 \ldots N\). Корова \(i\) имеет \(s_i\) - уровень мастерства в заворачивании
подарков. ФД решил объединить коров в команды. Команда состоит из любого
последовательного множества коров числом не более \(K\) коров (\(1 \leq K \leq 10^3\)),
и корова не может быть более чем в одной команде. Поскольку коровы могут учиться друг у друга, уровень мастерства каждой коровы в команде может быть заменен на уровень мастерства самой мастеровитой коровы.
Помогите ФД определить максимально возможную сумму уровней мастерства,
которую он может получить, оптимально сформировав команды.
ФОРМАТ ВВОДА (файл teamwork.in):
Первая строка ввода содержит \(N\) и \(K\). Следующие \(N\) строк содержат
уровни мастерства \(N\) коров в порядке как они стоят. Каждый уровень мастерства
это положительное целое число не более \(10^5\).
ФОРМАТ ВЫВОДА (файл teamwork.out):
Выведите наибольшую возможную сумму уровней мастерства, которую может получить ФД,
сгруппировав коров по командам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 3
1
15
7
9
2
5
10
|
84
|