Yan "the globe-trotter" Soares is traveling through Central Asia. In the city of Almaty, one of Kazakhstan's largest metropolises, he stumbled upon a curious arcade that is open 24 hours. As he enjoys games in general, he decided to enter the arcade and found a very peculiar claw machine.

Inside this machine, there are $$$N$$$ stuffed animals arranged in a row. Additionally, the claw used to grab the stuffed animals is also unique. This claw has two prongs, left and right. The distance between the prongs is exactly the width of $$$W$$$ stuffed animals (all stuffed animals have the same width).

Here's how the claw operates: Initially, the claw is above the stuffed animals. The player chooses the position of the left prong (the right prong is $$$W$$$ stuffed animals to the right of it). The claw descends until the prongs touch the row. Finally, the right prong moves to the left until it touches a stuffed animal (if there are $$$W$$$ stuffed animals between the two prongs, the right prong does not move). The claw then removes all the stuffed animals between the two prongs. The remaining stuffed animals stay in the same position, so the row will have gaps after using the claw. Note that the left prong cannot move to the left of the first stuffed animal, and the right prong cannot move to the right of the last stuffed animal in the row.

Yan has assigned a preference value $$$p_i$$$ to each stuffed animal in the row (this value can even be negative). He also has $$$M$$$ coins to play. Since he doesn't want to waste these coins, he asked for your help to determine the maximum total preference value he can achieve if he uses the claw up to $$$M$$$ times (he can choose not to use any coins at all). Help Yan find this maximum value!