题目描述

给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$ 以及两个整数 $m, k$。你可以选择至多 $m$ 个数，将选中的每个数增加 $k$。一个数至多被选择一次。求操作后所有数中最大值与最小值之差的最小值。

你需要最小化 $\max a'_i - \min a'_i$，其中 $a'_i$ 是操作后的数组。

输入格式

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

第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

输出格式

一行一个整数，表示操作后最大值与最小值之差的最小值。

2 2 10
8 9

1

3 2 10
1 10 12

2

4 1 5
2 6 9 11

5

样例解释

样例 $1$：不选择任何数做加法，最大值 $9$，最小值 $8$，差值为 $1$。

样例 $2$：选择第一个数加 $10$，变为 $[11,10,12]$，最大值与最小值的差为 $2$。

样例 $3$：不操作时最大值 $11$，最小值 $2$，差值为 $9$。选择 $2$ 加 $5$ 变为 $7$，数组变为 $[7,6,9,11]$，最大值 $11$，最小值 $6$，差值为 $5$，这是最优方案。

数据范围与约定

对于所有数据，$1 \le n \le 10^5$，$1 \le m \le n$，$1 \le k \le 10^5$，$1 \le a_i \le 10^9$。

下发样例

下发样例下载