P9064 [yLOI2023] Bitter Bamboo Grove

> The wind chimes hanging under the eaves sound pleasant as they sway. > Longing is like the endless plum rain, leaving my mood a muddy mess. > The scattered stars across the sky sparkle with the fate we share. > When maple leaves lightly fall into the heart of the lake, the nearby view is calm and peaceful. — Yin Lin & Han Yu, *Bitter Bamboo Grove*

There are $n$ wind chimes hanging under the eaves, and each wind chime can produce a sound of a certain pitch. Number the wind chimes from left to right from $1$ to $n$. The pitch of the $i$-th wind chime is $a_i$. To express his longing, Fusu decides to take $m$ out of the $n$ wind chimes and give them to a friend far away. Please find the minimum integer $\varepsilon$ such that there exists a way to choose $m$ wind chimes from the $n$ wind chimes. Let the pitches of the selected wind chimes be $b_1, b_2, \dots, b_m$. They must satisfy that for any $1 \leq i, j \leq m$, we have $|b_i - b_j| \leq \varepsilon$.

The first line contains two integers, representing the number of wind chimes $n$ and the number of wind chimes to select $m$. The second line contains $n$ integers, representing the pitch of each wind chime. The $i$-th integer is $a_i$.

Output one integer on a single line, representing the minimum $\varepsilon$.

### Explanation for Sample 2 One possible plan is to choose the $2, 4, 5, 6$-th wind chimes, with pitches $7, 3, 4, 6$ in order. Then for any $1 \leq i, j \leq 4$, we have $|b_i - b_j| \leq 4$. Another plan is to choose the $2, 3, 5, 6$-th wind chimes. The computed $\varepsilon$ is also $4$. ### Constraints - For $10\%$ of the testdata, $m = 2$. - For another $10\%$ of the testdata, $m = n$. - For $40\%$ of the testdata, $n \leq 5$. - For $60\%$ of the testdata, it is guaranteed that for all $2 \leq i \leq n$, $a_{i - 1} \leq a_i$, i.e., $a_i$ is non-decreasing. - For $80\%$ of the testdata, $n \leq 10^3$. - For $100\%$ of the testdata, $2 \leq m \leq n \leq 10^5$, and $1 \leq a_i \leq 10^9$. ### Notes This problem provides three additional sample files. See `ring.zip` in the attachments. Translated by ChatGPT 5