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

题目背景

大维正在研究一组数字，他可以对其中最多的几个数字进行调整，希望最终这组数字的最大值和最小值尽可能接近，从而更好地分析数据的离散程度。

题目描述

现在有 $n$ 个数字，大维至多可以挑选 $m$ 个数字（至少挑选 0 个），使得这些数字全部增加 $k$。

最终，大维希望最大的数字和最小的数字尽可能接近，请问最大的数字和最小的数字的差值最少是多少？

输入格式

第一行输入三个正整数 $n, m, k$。

第二行输入 $n$ 个正整数，第 $i$ 个数字为 $a_i$（$1 \le a_i \le 10^9$）。

输出格式

输出一行一个整数，表示最小的差值。

样例

2 2 10
8 9

1

3 2 10
1 10 12

2

样例解释

样例 1：不选择任何数字做加法，最大值为 9，最小值为 8，差值为 1。
样例 2：选择第一个数字加 10，变成 $$[11,,10,,12]$$ 三个数字，最大值和最小值的差距是 2。

数据范围

• 对于 30% 的数据，$m = 0$。
• 对于 50% 的数据，$m = 1$。
• 对于另外 20% 的数据，$k = 1$。
• 对于 100% 的数据，$1 \le n, m, k \le 10^5$。