Minimizing Magical Power Difference

You are given n creatures each with a magical power value and an integer k representing the number of spells you can cast. In one spell, you can choose the creature with the smallest power (if there are several, choose one arbitrarily) and increase its power instantly to match the maximum power among all creatures. You must cast exactly k spells. Your task is to determine the minimum possible difference between the strongest creature and the weakest creature after exactly k spells have been cast.

Note: If the number of creatures with power less than the maximum is less than or equal to k, then you can equalize all creatures and the difference will be 0.

Formulation: Let the creatures' powers be sorted in non-decreasing order as \(a_0 \le a_1 \le \cdots \le a_{n-1}\) with \(a_{n-1}\) the maximum. If there are \(c\) creatures such that \(a_i \lt a_{n-1}\) and if \(k \ge c\) then answer is 0; otherwise, you raise the smallest \(k\) powers to \(a_{n-1}\), and the minimum remaining power will be \(a_k\). The answer will be \(a_{n-1} - a_{k}\).

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains two integers n and k separated by a space, where n is the number of creatures and k is the number of spells you may cast. The second line contains n space-separated integers representing the magical powers of the creatures.

outputFormat

Output a single integer which is the minimum possible difference between the strongest and weakest creature after exactly k spells have been cast. The result should be printed to standard output (stdout).

5 3
5 3 8 7 10

2