Maximizing Difference in Array Elements with Moves

Each operation adds 1 to or subtracts 1 from any one element, at most K times in total. N is divisible by 3; maximize the N/3-th largest element minus the N/3-th smallest element.

This site uses a standard input/output protocol.

输入格式

The first line contains N K; the second line contains N integers. N is a multiple of 3 in 3..150000, K is in 0..500000000, and the elements are in −300000000..300000000.

输出格式

Output a single integer, the answer.

样例 1

输入：

6 3
6 6 6 6 6 6

输出：

1

样例 2

输入：

3 2
1 2 3

输出：

4

样例 3

输入：

12 1
8 8 8 7 7 7 7 7 7 7 -8 -8

输出：

1

样例说明

Example 1: both 6s must change to move the quantile by 1, so 3 steps can only increase the gap by 1. Example 2: the original gap is 2; lowering 1 to −1 makes the gap 4. Example 3: changing one 7 to 8 moves the upper quantile from 7 to 8 while the lower quantile stays at 7, for a gap of 1.