Super Chords

Little Z is a famous pianist. Recently, Dr. C presented him with a super piano which can play n distinct notes numbered from 1 to n. The i-th note has a beauty value \(A_i\) (which can be positive or negative).

A super chord is defined as a contiguous segment of notes whose length is at least \(L\) and at most \(R\). The beauty of a super chord is the sum of the beauty values of all the notes it contains. Two super chords are considered the same if and only if they contain exactly the same notes.

Little Z intends to create a piece of music consisting of exactly \(k\) super chords, with all chords distinct. The overall beauty of the piece is defined as the sum of the beauties of the chosen chords. Determine the maximum beauty that Little Z can achieve.

Note: The chords may overlap, but no chord (i.e. contiguous segment) can be chosen more than once.

inputFormat

The first line contains four integers: \(n\), \(L\), \(R\), and \(k\) — the number of notes, the minimum and maximum length of a super chord, and the number of chords to choose, respectively.

The second line contains \(n\) integers \(A_1, A_2, \dots, A_n\), where \(A_i\) is the beauty value of the \(i\)-th note.

outputFormat

Output a single integer, the maximum total beauty of the music piece composed of \(k\) super chords.

sample

5 1 3 2
1 2 3 4 5

21