Minimum Prize Difference

You are given n prizes and an integer m representing the number of participants. Your task is to distribute exactly m prizes selected from the given n prizes in such a way that the difference between the highest prize and the lowest prize among the selected prizes is minimized.

Formally, let the prizes be represented by an array prizes of n integers. You need to find a subarray (after sorting the prizes) of length m such that the value of $$\text{difference} = prizes[i+m-1]-prizes[i]$$

is minimized over all valid indices i. Output this minimum possible difference.

inputFormat

The input is given via standard input (stdin) and consists of two lines.

• The first line contains two space-separated integers n and m, where n is the total number of prizes, and m is the number of participants.
• The second line contains n space-separated integers representing the prize values.

outputFormat

Output a single integer to standard output (stdout) – the minimum possible difference between the maximum and minimum prize values among any subset of m prizes.

6 4
8 12 5 7 9 10

3