You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

悬挂在屋檐下的风铃，摇晃的声音很动听。
思念就像梅雨下不停，我的心境一片泥泞。
散落在天际里的繁星，闪烁着你我的宿命。
当枫叶轻盈落入湖心，近看山水一片宁静。

——银临 & 涵昱《苦竹林》

题目描述

共有 $n$ 个风铃悬挂在屋檐下，每个风铃都能发出一定音调的声音。从左到右给风铃从 $1$ 至 $n$ 编号，第 $i$ 个风铃的音调是 $a_i$。

为了表达内心的思念，扶苏决定在 $n$ 个的风铃中取出 $m$ 个，送给远方的朋友。

请你找到最小的整数 $\varepsilon$，使得存在一种方案，能够从 $n$ 个风铃中挑出 $m$ 个，设挑出风铃的音调为 $b_1, b_2, \dots b_m$，满足对任意的 $1 \leq i, j \leq m$，都有 $|b_i - b_j| \leq \varepsilon$。

输入格式

第一行是两个整数，表示风铃的个数 $n$ 和挑选出风铃的个数 $m$。
第二行有 $n$ 个整数，表示每个风铃的音调。第 $i$ 个整数表示 $a_i$。

输出格式

输出一行一个整数，表示最小的 $\varepsilon$。

5 3
1 2 3 4 5

2

6 4
1 7 8 3 4 6

4

提示

样例 2 解释

一种选择的方案是选择第 $2,4,5,6$ 四个风铃，音调依次为 $7,3,4,6$。可以得到对任何的 $1 \leq i, j\leq 4$，都有 $|b_i - b_j| \leq 4$。

另一种方案是选择第 $2,3,5,6$ 四个风铃，同样计算得到的 $\varepsilon$ 为 $4$。

数据规模与约定

• 对 $10\%$ 的数据，$m = 2$。
• 另有 $10\%$ 的数据，$m = n$。
• 对 $40\%$ 的数据，$n \leq 5$。
• 对 $60\%$ 的数据，保证对所有的 $2 \leq i \leq n$，满足 $a_{i - 1} \leq a_i$，即 $a_i$ 单调不降。
• 对 $80\%$ 的数据，$n \leq 10^3$。
• 对 $100\%$ 的数据，$2 \leq m \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。

说明

本题共有三个附加样例文件，见题目附件中的 ring.zip。