#1446. [yLOI2023] 苦竹林

[yLOI2023] 苦竹林

题目描述

共有 nn 个风铃悬挂在屋檐下,每个风铃都能发出一定音调的声音。从左到右给风铃从 11 至 nn 编号,第 ii 个风铃的音调是 aia_i。

为了表达内心的思念,扶苏决定在 nn 个的风铃中取出 mm 个,送给远方的朋友。

请你找到最小的整数 ε\varepsilon,使得存在一种方案,能够从 nn 个风铃中挑出 mm 个,设挑出风铃的音调为 b1,b2,…bmb_1, b_2, \dots b_m,满足对任意的 1≤i,j≤m1 \leq i, j \leq m,都有 ∣bi−bj∣≤ε|b_i - b_j| \leq \varepsilon。

输入格式

第一行是两个整数,表示风铃的个数 nn 和挑选出风铃的个数 mm。
第二行有 nn 个整数,表示每个风铃的音调。第 ii 个整数表示 aia_i。

输出格式

输出一行一个整数,表示最小的 ε\varepsilon。

样例

5 3
1 2 3 4 5
2
6 4
1 7 8 3 4 6
4

题目来源:洛谷 P9064