Description

Xiao Xue and Xiao Keke are playing a number game. They have prepared $n$ cards, each with an integer on it. At the beginning, Xiao Xue chooses an integer $t$ with $a \le t \le b$ and tells Xiao Keke the value of $t$. Then Xiao Keke selects exactly $k$ cards and sums their numbers; denote this sum by $m$.

Xiao Xue wants the absolute difference between $t$ and $m$ to be as large as possible, while Xiao Keke wants it to be as small as possible. Before the game starts, both of them know $n$, $a$, $b$, and $k$, and also the number on every card. After Xiao Xue decides $t$, it cannot be changed, and only then does Xiao Keke select the cards.

Xiao Xue wants to know, under optimal play by both of them, how large the absolute difference between $t$ and $m$ can be.

Input Format

The input has 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, namely $x_1$ to $x_n$, which are the numbers on the cards.

Each number $x_i$ satisfies $0 \le x_i \le 300$.

Output Format

Output one line with a single integer, which is the maximum possible value of the absolute difference between $t$ and $m$.

4 2 58 100
10 10 50 80

15

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

1782

Hint

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

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

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

Translated by ChatGPT 5