Module: Prefix sums


Problem

3 /8


Quiet don №2

Problem

Aksinya loves Gregory, but she is married to Stepan. She is unhappy with her husband, so the time she spends with him can be characterized by a negative indicator of Aksinya's happiness (\(a_i < 0\)), and the time that she spends with Gregory, a positive indicator of happiness (\(a_i > 0\)). It is known that Aksinya spends one day either with her husband or with her lover. 

Find the maximum total happiness for L days in which Aksinya will spend no more than C days with her husband.
 
Input
The first line contains 3 numbers: N – number of days, L and C (\(1 <= L, C <= N <= 1 000 000\)).
The second line contains N numbers a_i (\(1 <= |a_i| <= 1,000,000 000\)).

Input
You want to display the answer to the problem.
 

 

Examples
# Input Output
1 5 3 3
1 -1 2 -2 3
3