Cole, who is trying to make the most of his last year of elementary school, has an array $$$a$$$ of $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ plates of chicken stars arranged in a straight line in his backyard.
Unfortunately for Cole, Barney the Dinosaur has just arrived—and he's furious that Cole chose chicken stars over dinosaur nuggets. In a fit of rage, Barney decides to stomp on a contiguous sequence of plates.
Formally, Barney will choose one subarray of length $$$k$$$ $$$(1 \leq k \leq n)$$$ and stomp on it, destroying all of the chicken stars in this subarray.
Cole, acting quickly, can save the chicken stars from one plate before Barney stomps. That is, he can choose one index $$$i$$$ and set $$$a_i = 0$$$ before Barney makes his move.
Barney wants to maximize the number of chicken stars he stomps on while Cole wants to minimize it. Assuming both perform their actions optimally, how many chicken stars will Barney stomp on?
The first line contains integers $$$n, k$$$ $$$(1 \leq k \leq n \leq 10^5)$$$ where $$$n$$$ the size of $$$a$$$ (number of plates of chicken stars) and $$$k$$$ is the length of the subarray that Barney will stomp on.
The second line contains $$$n$$$ integers, $$$[a_1, a_2, ... a_n]$$$ $$$(1 \leq a_i \leq 10^9$$$), the elements in $$$a$$$.
Output one number, the number of chicken stars Barney will stomp on.
5 33 5 7 4 7
11
4 41 10 4 8
13
In the first test case, one set of actions that results in the provided answer is:
Cole saves plate $$$i = 3$$$, setting $$$a_3 = 0$$$ Barney stomps on subarray $$$[3...5]$$$ $$$0 + 4 + 7 = 11$$$
In the second test case, one set of actions that results in the provided answer is:
Cole saves plate $$$i = 2$$$, setting $$$a_2 = 0$$$ Barney stomps on subarray $$$[1...4]$$$ (this is his only option) $$$1 + 0 + 4 + 8 = 11$$$
