Little Z is a moderately famous pianist. Recently, Dr. C gifted Little Z a "super piano," and Little Z hopes to use this piano to compose the most beautiful music in the world.

This super piano can play $n$ notes, numbered from $1$ to $n$. The beauty of the $i$-th note is $A_i$, where $A_i$ can be positive or negative.

A "super chord" consists of a sequence of consecutive notes, with the number of notes being no less than $L$ and no more than $R$. We define the beauty of a super chord as the sum of the beauty of all the notes it contains. Two super chords are considered identical if and only if the set of notes they contain is the same.

Little Z decides to compose a piece of music consisting of $k$ super chords. To make the music more pleasant, Little Z requires that the piece be composed of $k$ distinct super chords. We define the beauty of a piece of music as the sum of the beauty of all the super chords it contains. Little Z wants to know the maximum possible beauty of a piece of music he can compose.

Input

The first line contains four positive integers $n, k, L, R$. Here, $n$ is the number of notes, $k$ is the number of super chords in the music, and $L$ and $R$ are the lower and upper bounds on the number of notes in a super chord, respectively.

The next $n$ lines each contain an integer $A_i$, representing the beauty of each note in order of their index.

Output

Output a single integer representing the maximum beauty of the music.

Examples

Input 1

4 3 2 3
3
2
-6
8

Output 1

11

Note

There are 5 different super chords: 1. Notes 1 ~ 2, beauty $3 + 2 = 5$ 2. Notes 2 ~ 3, beauty $2 + (-6) = -4$ 3. Notes 3 ~ 4, beauty $(-6) + 8 = 2$ 4. Notes 1 ~ 3, beauty $3 + 2 + (-6) = -1$ 5. Notes 2 ~ 4, beauty $2 + (-6) + 8 = 4$

The optimal solution is to compose the music using chord 1, chord 3, and chord 5, with a total beauty of $5 + 2 + 4 = 11$.