# 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 $n$ 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 $x$ banana trees and the difference of position between any two trees among these chosen x trees should be less than $k$. He collected all bananas of those $x$ 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 $f$ fresh bananas and $r$ rotten bananas. What is the maximum value of $(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 (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 $n$ integers $a_1, a_2,a_3... , a_n (-10^6 ≤ a_i ≤ 10^6)$ the bananas in the $i^{th}$ tree (Here, $(a_i<0)$ means that the $i^{th}$ tree contains $\lvert a_i \rvert$ rotten bananas. And $(a_i\geq 0)$ means that the $i^{th}$ tree contains $\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]$ the monkey can choose trees at the positions $4$ and $5$. These two trees both contain rotten bananas and he cannot convert them into fresh bananas as he has $0$ magic spells. So,total rotten bananas, $r=1+2=3$, total fresh bananas, $f=0$. The value of $(f-r)=0-3=-3$. We can show that this is the maximum value of $(f-r)$.

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

### Statistics

100% Solution Ratio

ashraful9194Earliest, 2M ago

Deshi_TouristFastest, 0.1s

ashraful9194Lightest, 7.3 MB

Deshi_TouristShortest, 2305B

### Related Contests

 Code To Save A MotherEnded 2M ago