408759: GYM103295 G Spar-Lord's Voyage

Wicked Thamos is plotting to take over the universe after he becomes extremely powerful by collecting all of the legendary Eternity Rocks. However, our hero Spar-Lord refuses to let that happen without putting up a fight! Spar-Lord wants to obtain as many Eternity Rocks as possible, to keep them out of Thamos's possession.

Spar-Lord has planned out a space voyage to visit $$$N$$$ planets in order before he will finally rendezvous with the rest of his crew—the Custodians of the Galaxy. On the $$$i^{th}$$$ planet, Spar-Lord has the opportunity to obtain $$$r_i$$$ Eternity Rocks if he descends onto the planet and battles the enemies that are hoarding the rocks. However, if he does so, he will need to spend some time on his ship recovering from the battle, so he will not be able to descend onto any of the next $$$k$$$ planets, with indices $$$i+1$$$ through $$$i+k$$$. Spar-Lord also has the option to descend onto the $$$i^{th}$$$ planet for only a quick skirmish, where he will obtain $$$\frac{r_i}{2}$$$ Eternity Rocks rounded down to the nearest integer but only need to recover from the battle while passing over the next $$$\frac{k}{2}$$$ planets, also rounded down to the nearest integer. Of course, Spar-Lord can always choose not to descend onto a planet, and save his energy for a future, more critical battle.

Help Spar-Lord make the right choices to obtain as many Eternity Rocks as possible! Output the maximum number of Eternity Rocks that Spar-Lord will be able to collect.

The first line of input contains the integers $$$N$$$ and $$$k$$$ ($$$1 \leq k \leq N \leq 10^6 $$$), denoting the number of planets on Spar-Lord's voyage and his battle recovery constant respectively. The next line contains $$$N$$$ space-separated integers $$$r_0$$$ through $$$r_N$$$, where $$$r_i$$$ $$$(0 \leq r_i \leq 10^3)$$$ is the number of Eternity Rocks available on the $$$i^{th}$$$ planet.

Print the maximum number of Eternity Rocks that Spar-Lord should be able to accumulate along his space voyage.

8 2
135 466 904 575 492 259 796 317

1767