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.

时空限制

1S/512M

题目描述

apiadu 养了 $n$ 只兔子，他把兔子们放到一个街道上玩耍，街道可以看成一个数轴，初始时第 $i$ 只兔子的坐标为 $a_i$（可能有多只兔子在同一坐标），每只兔子的移动速度都为每秒最多 $1$ 单位长度。

apiadu 为了给它们喂食，想让它们在某一坐标位置集合，apiadu 可以让它们在任意一个整数坐标集合，每秒都可以同时向所有兔子下达指令让每只兔子向任意指定方向移动最多 $1$ 单位长度（也可以原地不动）。为了加快集合速度，apiadu 可以使用最多 $k$ 次魔法，每次使用魔法可以选定一只兔子，使它向任意指定方向瞬间移动最多 $x$ 单位长度，每只兔子最多选定一次。

现在 apiadu 想要知道，在合理地选择集合地点、下达指令、使用魔法后，最少需要多少秒才能使所有兔子在同一坐标集合？请你帮助他，可以证明答案为整数。

保证所有兔子的初始坐标 $a_i$ 与单次魔法的最长顺移距离 $x$ 都为偶数。

格式

输入格式

第一行包含三个整数 $n,k,x$，分别表示兔子的数量、魔法的最多使用次数和单次魔法的最长顺移距离。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每只兔子的初始位置。

输出格式

输出一个整数，表示所有兔子集合的最少时间是多少秒。

样例

样例输入 #1

5 2 4
0 2 4 6 12

样例输出 #1

3

样例输入 #2

6 2 6
0 4 4 18 24 26

样例输出 #2

10

样例输入 #3

6 6 6
6 6 6 6 6 6

样例输出 #3

0

样例输入 #4

10 2 170
26 186 198 416 504 524 662 722 886 922

样例输出 #4

350

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据：$1 \le n \le 10^5$，$0 \le k \le n$，$0 \le x \le 10^9$，$0 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$，保证所有 $a_i$ 和 $x$ 均为偶数。