is playing the new hit game, Gremlin Impact.
In Gremlin Impact, the rarest drop in the game, silver, is obtained by completing the final map. ~N~ days. Every day the amount of silver awarded for completion changes and is denoted by ~a_i~. Additionally, after completing the final map, it requires ~K~ days to replenish its resources before it can be completed again. This means that if the map is completed on day ~i~ and ~K=0~, can complete another run on day ~i+1~. Impatient to wait the full ~K~ days, he purchased a booster that allows him to bypass the previous rule one time. Boosters are expensive so wants to make the most of it.is trying to farm as much silver as he can over the next
Can you help him farm the most silver in ~N~ days?
The first line contains two space-separated integers ~N, K (0 \le K < N \le 2 \cdot 10^5)~
The second line contains ~N~ integers, the silver awarded for completion of the final map on a given day, ~a_1, a_2, ... , a_N (1 \le a_i \le 10^4)~
Output a single integer, the maximum amount of silver thatcan farm.
Subtask 1 (20%)
~N \le 1000~
Subtask 2 (80%)
No further constraints.
Sample Input 1
6 3 5 5 5 5 5 5
Sample Output 1
Sample Input 2
11 2 1 5 2 1 4 6 7 3 2 1 2
Sample Output 2