Byteman wants to go for a vacation and he would like to select the best days for that.
He bases his choices on a weather forecast for the next days.
He is only interested in the highest temperature anticipated for a given day.
Byteman is additionally constrained by terms set by his boss.
During any consecutive days he can take no more than days of absence.
What is the best way to plan the vacation, so that the sum of temperatures in the selected days is maximized?
Input
The first line of the input contains two integers and (, , ).
In the second line there are positive integers not exceeding
that describe the temperatures anticipated for each of the next days.
Output
Your program should output a single integer:
the maximum possible sum of temperatures during vacation days picked with respect to boss' terms.
Example
For the input data:
5 3
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35
the correct result is:
195
Task author: Jakub Pachocki.
Kontakt
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.