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

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.

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).

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 $[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)$.

100% Solution Ratio

ashraful9194Earliest,

Deshi_TouristFastest, 0.1s

ashraful9194Lightest, 7.3 MB

Deshi_TouristShortest, 2305B

Login to submit