Paul loves the song Never Gonna Give You Up and often plays it on his laptop at maximum volume for his friends to enjoy too.

However, Paul thinks that the maximum volume on his laptop is not loud enough. So, he has bought a huge boombox with ~N~ speakers on it to play the song. The speakers are arranged evenly in a row, where the distance between every pair of adjacent speakers is ~1~ metre. To better identify these speakers, Paul has numbered them ~1, 2, ..., N~ in order and has given each one an integer value ~a_i~ representing its relative loudness.

Even with the boombox, Paul finds that the sound is not loud enough. So, he has borrowed ~M~ batteries from his friend to amplify the speakers. Each battery can amplify a single speaker and will increase its loudness by a factor of ~B~. Each speaker may be amplified at most once.

Paul would like to amplify speakers in a way that maximizes the final sum of the loudness values. However, to protect his ears, Paul will not amplify two speakers if they are strictly less than ~K~ metres away.

Please help Paul find the maximum possible sum if he can amplify up to ~M~ speakers.

Input Specification

The first line of input will contain four space-separated integers, ~N~ ~(1 \le N \le 10^4)~, ~M~ ~(1 \le M \le N)~, ~K~ ~(1 \le K \le N)~, and ~B~ ~(1 \le B \le 200)~.

The next line will contain ~N~ space-separated integers, ~a_1, a_2, ..., a_N~ ~(1 \le a_i \le 200)~.

Subtask 1 [20%]

~M = 2~

~1 \le N \le 500~

Subtask 2 [30%]

~1 \le N \le 500~

Subtask 3 [50%]

No additional constraints.

Output Specification

Output a single integer, the maximum sum of the loudness values after amplifying up to ~M~ speakers.

It is guaranteed that the answer will fit in a 32-bit integer.

Sample Input 1

5 3 3 2
1 4 8 3 5

Sample Output 1

30

Explanation for Sample Output 1

Paul can amplify speakers ~2~ and ~5~ (which are ~3~ metres apart) to get the sum ~1 + 4 \cdot 2 + 8 + 3 + 5 \cdot 2 = 30~.

Sample Input 2

8 4 2 3
1 8 2 8 6 7 9 1

Sample Output 2

92

Explanation for Sample Output 2

Paul can amplify speakers ~2~, ~4~, and ~7~ to get a sum of ~92~.