Limits 1s, 512 MB

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 nn 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 xx banana trees and the difference of position between any two trees among these chosen x trees should be less than kk. He collected all bananas of those xx 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 ff fresh bananas and rr rotten bananas. What is the maximum value of (fr)(f-r) the monkey could get?

Note: See the input-output section & explanation of sample output for more clarification.

Input

The first line contains four integers n,k,x,c (1xkn105,0c105)n,k,x,c (1≤ x≤ k≤ n≤ 10^5,0≤ c≤ 10^5), 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 nn integers a1,a2,a3...,an (106ai106)a_1, a_2,a_3... , a_n (-10^6 ≤ a_i ≤ 10^6) the bananas in the ithi^{th} tree (Here, (ai<0)(a_i<0) means that the ithi^{th} tree contains ai\lvert a_i \rvert rotten bananas. And (ai0)(a_i\geq 0) means that the ithi^{th} tree contains ai\lvert a_i \rvert fresh bananas).

Output

Print the desired answer in a single line.

Samples

InputOutput
5 3 2 0
-1 -9 -3 -1 -2
-3
InputOutput
5 3 2 1
-3 -6 3 -8 10
18

Explanation of sample output 01: In the range [3,5][3,5] the monkey can choose trees at the positions 44 and 55. These two trees both contain rotten bananas and he cannot convert them into fresh bananas as he has 00 magic spells. So,total rotten bananas, r=1+2=3r=1+2=3, total fresh bananas, f=0f=0. The value of (fr)=03=3(f-r)=0-3=-3. We can show that this is the maximum value of (fr)(f-r).

Explanation of sample output 02: In the range [3,5][3,5] the monkey can choose trees at the positions 44 and 55. The tree at position 44 has rotten bananas while the tree at position 55 has fresh bananas. The monkey can spend his one spell in the tree at position 44 to convert them into fresh bananas. So, total fresh bananas, f=8+10=18f=8+10=18, total rotten bananas, r=0r=0. The value of (fr)=180=18(f-r)=18-0=18.We can show that this is the maximum value of (fr)(f-r).

Submit

Login to submit.

Contributors

Statistics

100% Solution Ratio
ashraful9194Earliest, May '21
nusuBotFastest, 0.1s
ashraful9194Lightest, 7.3 MB
Deshi_TouristShortest, 2305B
Toph uses cookies. By continuing you agree to our Cookie Policy.