该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小明最近在实验室里做生理盐水混合实验，发现手头上有 $n$ 瓶酸碱度各不相同的生理盐水。为了便于储存，他想把这 $n$ 瓶盐水重新装入 $k$ 个空瓶中。同一瓶中混合的盐水要求酸碱度完全相同，但现有盐水的酸碱度并不统一。为了解决这个问题，小明准备向哆啦A梦的杂货铺购买道具“酸碱度修改器”，该道具可以对盐水的酸碱度进行微调。

题目描述

小明有 $n$ 瓶生理盐水，第 $i$ 瓶的酸碱度为 $a_i$。他想把这 $n$ 瓶盐水重新灌装到 $k$ 个瓶子里，每个瓶子里混合的盐水酸碱度必须完全一致。为了让更多瓶次能够混合，他可以对每一瓶盐水使用一次“酸碱度修改器”将其酸碱度增加或减少至一个新的值，最大改变量为 $m$。即属性值为 $m$ 的“酸碱度修改器”可以将原酸碱度为 $a_i$ 的盐水修改到任意 $[\,a_i - m,\;a_i + m\,]$ 整数范围内的值。每瓶盐水最多使用一次修改器，而同一支“酸碱度修改器”可以重复用于不同的盐水。

小明希望购买尽可能小的属性值 $m$ 的“酸碱度修改器”，以保证最终能将这 $n$ 瓶盐水分成恰好 $k$ 组，每组内的酸碱度一致。请计算最小需要的 $m$。

输入格式

第一行包含两个正整数 $n, k$。
第二行包含 $n$ 个正整数，依次表示 $a_1, a_2, \dots, a_n$。

输出格式

输出一个整数，表示最小需要的属性值 $m$。

样例

4 2
1 3 5 7

1

4 1
1 3 5 7

3

样例解释

样例1：将酸碱度为 1、3 的两瓶分别修改为 2，再混合成一组；将酸碱度为 5、7 的两瓶分别修改为 6，混合成另一组。此时只需 $m=1$。

样例2：需要将所有 4 瓶盐水混合到同一瓶中，原酸碱度分别是 1、3、5、7，最终要让它们都相同。最优方案是将它们都调整到 4，此时最大的改变量为 $3$。

数据范围

• 对于 30% 的数据，$n \le 20$。
• 对于 50% 的数据，$n \le 500$。
• 对于 20% 的数据，$k = 2$。
• 对于 100% 的数据，$n \le 10^5$，$1 \le a_i \le 10^9$。

附件