Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Rational Monkey

By ashraful9194 · 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).

    Discussion

    Statistics


    100% Solution Ratio

    ashraful9194Earliest, 1w ago

    ashraful9194Fastest, 0.1s

    ashraful9194Lightest, 7.3 MB

    ashraful9194Shortest, 2306B

    Submit

    Login to submit

    Related Contests