题目描述

一场别开生面的徒步露营大会就要在小珅的营地举办了！

来自各地的徒步队员将会到达当地的车站，前来参会并露营。具体地说，有 $N$ 名徒步队员到达了车站（$1 \le N \le 10^5$），其中队员 $i$ 在时间 $t_i$（$0 \le t_i \le 10^9$）到达。小珅安排了 $M$（$1 \le M \le 10^5$）辆大巴来车站接这些队员。每辆大巴可以乘坐 $C$ 名队员（$1 \le C \le N$）。小珅正在车站等待队员们到来，并且准备安排到达的队员们乘坐大巴。当最后一名队员乘坐某辆大巴的队员到达的时候，这辆大巴就可以发车了。小珅想要做一个优秀的主办方，所以并不想让队员们在车站等得过长的时间。如果小珅合理地协调这些大巴，等待时间最长的队员等待的时间的最小值是多少？

一名队员的等待时间等于她的到达时间与她乘坐的大巴的发车时间之差。

输入保证 $M C \ge N$。

输入格式

输入的第一行包含三个空格分隔的整数 $N, M, C$。

第二行包含 $N$ 个空格分隔的整数，表示每名队员到达的时间。

输出格式

输出一行，包含所有到达的队员中的最大等待时间的最小值。

输入输出样例

6 3 2
1 1 10 14 4 3

4

6 3 3
1 1 100 100 100 1000000000

0

说明/提示

说明/提示

样例 1：如果两头时间 $1$ 到达的队员乘坐一辆巴士，时间 $3$ 和时间 $4$ 到达的队员乘坐第二辆，时间 $10$ 和时间 $14$ 到达的队员坐第三辆，那么等待时间最长的队员等待了 $4$ 个单位时间（时间 $10$ 到达的队员从时间 $10$ 等到了时间 $14$）。

样例 2：两头时间 $1$ 到达的队员乘坐一辆巴士；三头时间 $100$ 到达的队员乘坐第二辆巴士；最后一头时间 $1000000000$ 到达的队员乘坐第三辆巴士；就可以让每头队员都无需等待。

数据范围

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le M \le 10^5$，$1 \le C \le N$，$0 \le t_i \le 10^9$，保证 $M C \ge N$。

1 1 1
0

0