Maximizing Absolute Difference in a Card Game

XiaoXue and XiaoKeKe are playing a numerical card game. There are \(n\) cards, each with an integer. When the game starts, XiaoXue chooses an integer \(t\) such that \(a \le t \le b\), and announces it. Then XiaoKeKe selects exactly \(k\) cards, and the sum of the numbers on these cards is denoted by \(m\).

XiaoXue wants to maximize the absolute difference \(|t-m|\), while XiaoKeKe wants to minimize it. Both players know the values of \(n\), \(a\), \(b\), \(k\) and the number on each card. Once XiaoXue has chosen \(t\), it cannot be changed, and then XiaoKeKe makes the selection.

Assuming both players use optimal strategies, determine the maximum possible value of \(|t-m|\).

inputFormat

The first line of input contains four integers: (n), (a), (b), and (k). The second line contains (n) integers, representing the numbers written on the cards.

outputFormat

Output a single integer representing the maximum absolute difference (|t-m|) when both players play optimally.

sample

5 1 10 2
1 2 3 4 5

2