题目描述

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

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

输入格式

第一行输入三个正整数 $n,m,k$ 意义如题面所示。

第二行输入 $n$ 个正整数，第 $i$ 个数字为 $a_i(1 \leq a_i \leq 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 \leq n,m,k \leq 10^5$