National Olympiad in Informatics, China, 2010

Little Z is a minorly famous pianist. Recently, Doctor C has gifted him with a super piano. With it, little Z hopes to create the world's most enchanting music.

The super piano has ~n~ different keys in a row, numbered from ~1~ to ~n~. The value of the ~i~-th key is ~A_i~, where ~A_i~ can be positive or negative.

A chord consists of a sequence of between ~L~ and ~R~ consecutive keys. Two chords are considered the same if they contain the same sequence of notes.

We define the value of a chord as the sum of the values of all its notes.

Little Z decides to compose a piece consisting of ~k~ different chords. Note that the chords are independent, so may overlap. Find the maximum sum of values of these chords.

Input Specification

The first line contains four positive integers ~n~, ~k~, ~L~, and ~R~. ~n~ represents the number of keys on the super piano. ~k~ represents the number of different chords that the piece should consist of. ~L~ and ~R~ respectively represent the minimum and maximum number of keys that can be in a single chord.

The next ~n~ lines each contain one integer, with the ~i~-th line containing ~A_i~.

Output Specification

The output consists of a single integer, the maximum possible value of a piece that little Z can compose.

Sample Input

4 3 2 3
3
2
-6
8

Sample Output

11

Explanation

There are ~5~ possible super chords:

1. Notes ~1~ to ~2~, for a total value of ~3 + 2 = 5~
2. Notes ~2~ to ~3~, for a total value of ~2 + (-6) = -4~
3. Notes ~3~ to ~4~, for a total value of ~(-6) + 8 = 2~
4. Notes ~1~ to ~3~, for a total value of ~3 + 2 + (-6) = -1~
5. Notes ~2~ to ~4~, for a total value of ~2 + (-6) + 8 = 4~

The maximum value chords are ~1~, ~3~, and ~5~, for a total of ~5 + 2 + 4 = 11~.

Constraints

There are ~10~ total test cases with bounds satisfying:

Test Case	~N~	~k~
~1~	~\le 10~	~\le 100~
~2~	~\le 1\,000~	~\le 500\,000~
~3~	~\le 100\,000~	~= 1~
~4~	~\le 10\,000~	~\le 10\,000~
~5~	~\le 500\,000~	~\le 10\,000~
~6~	~\le 80\,000~	~\le 80\,000~
~7~	~\le 100\,000~	~\le 100\,000~
~8~	~\le 100\,000~	~\le 500\,000~
~9~	~\le 500\,000~	~\le 500\,000~
~10~	~\le 500\,000~	~\le 500\,000~

All of the test cases satisfy ~-1000 \le A_i \le 1000~ and ~1 \le L \le R \le n~.
Furthermore, it is guaranteed that a composition fitting the requirements will exist.

Problem translated to English by Alex, editted by rpeng.