Guitar Hero#608
Vasya recently bought himself an exciting game called "Guitar Hero." In this game, players can try themselves as a rock guitarist. To play through the game, it is necessary to press certain button combinations every second. Fortunately, the combinations are not many. If the necessary buttons are pressed, the player correctly plays the note and receives a certain number of points (the number of points can be different for each note, and for some notes, points can be negative). Otherwise, an unpleasant sound is heard and no points are awarded.
Vasya easily passed the first and second difficulty levels. However, upon reaching the third level, he encountered a particularly complicated composition that he could not perform. After several unsuccessful attempts, Vasya realized that he can correctly play any segment of or fewer notes, no matter how difficult they are. However, he cannot correctly play k + 1 notes in a row, even if they are very simple. He cannot explain why this happens. However, after a short search on the Internet, he found detailed information about the number of points awarded for each note if played correctly. Using this information, Vasya wants to determine the maximum number of points he can obtain. Help Vasya.
The first line contains two integers and (1 \le n \le 10000, 1 \le k \le 1000), where is the number of notes in the composition. The second line contains integers, representing the number of points for each note if played correctly. All numbers have absolute values not exceeding 10^9.
Output one number — the maximum total number of points that Vasya can obtain.
Example 1
Example 2
Example 3