Minimum Token Difference

You are given n participants with an initial number of tokens and an extra k tokens that may be used in the process. The goal is to achieve the minimum possible difference between the maximum and minimum token counts among all participants after performing a redistribution.

More formally, you are given two integers \(n\) and \(k\) and an array of integers \(a_1, a_2, \dots, a_n\) representing the initial tokens. You are allowed to perform operations (interpreted by the solution algorithm) to minimize the difference \(D = \max(a_i') - \min(a_i')\), where \(a_i'\) are the token counts after the redistribution. All formulas are given in \(\LaTeX\) format. The redistribution process follows a method that is verified by the sample tests below.

Note: The redistribution is done in such a way that a binary search is used to decide the minimum possible difference \(D\) while ensuring that a condition based on the available extra tokens \(k\) is met. The condition is checked by ensuring that the total amount by which some token counts exceed a given threshold does not surpass \(k\). It is guaranteed that an optimal solution exists.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains two space-separated integers \(n\) and \(k\), where \(n\) is the number of participants and \(k\) is the number of extra tokens available.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the initial token counts for each participant.

outputFormat

Output to stdout a single integer: the minimum possible difference between the maximum and minimum token counts after the optimal redistribution.

3 5
5 7 10

1