There lived a wise monkey in the forest of Amazon. One day he started searching the jungle for bananas as he was very hungry. Suddenly he saw a line of banana trees (numbered from 1 to n). He was very wise that’s true but he was a bit lazy as well. For that reason, he decided that he would collect bananas from exactly banana trees and the difference of position between any two trees among these chosen x trees should be less than . He collected all bananas of those banana trees.
However, It’s not necessary that the bananas will be fresh. They can be rotten as well. The monkey has also c magic spells. He can use these spells not more than c times. He can convert any tree containing rotten bananas to a tree of fresh bananas using just one magic spell.
Let, the monkey collected fresh bananas and rotten bananas. What is the maximum value of the monkey could get?
Note: See the input-output section & explanation of sample output for more clarification.
The first line contains four integers , the number of banana trees, the range, the number of trees the monkey decided to choose and the number of magic spells, respectively. The following line contains integers the bananas in the tree (Here, means that the tree contains rotten bananas. And means that the tree contains fresh bananas).
Print the desired answer in a single line.
Input | Output |
---|---|
5 3 2 0 -1 -9 -3 -1 -2 | -3 |
Input | Output |
---|---|
5 3 2 1 -3 -6 3 -8 10 | 18 |
Explanation of sample output 01: In the range the monkey can choose trees at the positions and . These two trees both contain rotten bananas and he cannot convert them into fresh bananas as he has magic spells. So,total rotten bananas, , total fresh bananas, . The value of . We can show that this is the maximum value of .
Explanation of sample output 02: In the range the monkey can choose trees at the positions and . The tree at position has rotten bananas while the tree at position has fresh bananas. The monkey can spend his one spell in the tree at position to convert them into fresh bananas. So, total fresh bananas, , total rotten bananas, . The value of .We can show that this is the maximum value of .