Problem Description

Xiaoxue and Xiaoke are playing a number game. They have prepared $n$ cards, each with an integer on it. At the start of the game, Xiaoxue will choose an integer $t$ that is not less than $a$ and not greater than $b$, and tell Xiaoke this number $t$. Then, Xiaoke will select exactly $k$ cards and sum the numbers on these $k$ cards to get a sum $m$.

Xiaoxue wants the absolute difference between $t$ and $m$ to be as large as possible, while Xiaoke wants the absolute difference between $t$ and $m$ to be as small as possible. Before the game starts, both of them know the values of $n$, $a$, $b$, and $k$, as well as the numbers on each card. After Xiaoxue decides the value of $t$, it cannot be changed, and then Xiaoke will select the cards.

Xiaoxue wants to know, under the optimal strategies of both players, what is the maximum possible absolute difference between $t$ and $m$?

Input Format

The input consists of two lines.

The first line contains 4 integers $n$, $k$, $a$, and $b$, satisfying $1 \le k \le n \le 250$ and $0 \le a \le b \le 75000$.

The second line contains $n$ integers, representing the numbers on each card from $x_1$ to $x_n$.

Each card's number $x_i$ satisfies $0 \le x_i \le 300$.

Output Format

Output a single line with a single integer, representing the maximum possible absolute difference between $t$ and $m$.

Sample Input and Output

Sample Input #1

4 2 58 100
10 10 50 80

Sample Output #1

15

Sample Input #2

8 3 1300 1800
2 0 1 9 1 4 0 5

Sample Output #2

1782

Notes/Hints

For 30% of the data, $1 \le k \le n \le 20$ and $0 \le a \le b \le 6000$.

For 80% of the data, $1 \le k \le n \le 65$ and $0 \le a \le b \le 19650$.

For 100% of the data, $1 \le k \le n \le 250$ and $0 \le a \le b \le 75000$.

见题面 Input 部分

见题面 Output 部分