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.

题目描述

​ 一场别开生面的牛吃草大会就要在 Farmer John 的农场举办了！

​ 世界各地的奶牛将会到达当地的机场，前来参会并且吃草。具体地说，有 $N$ 头奶牛到达了机场（$1\le N\le 10^5$），其中奶牛 $i$ 在时间 $t_i$（$0\le t_i\le 10^9$）到达。Farmer John 安排了 $M$（$1\le M\le 10^5$）辆大巴来机场接这些奶牛。每辆大巴可以乘坐 $C$ 头奶牛（$1\le C\le N$）。Farmer John 正在机场等待奶牛们到来，并且准备安排到达的奶牛们乘坐大巴。当最后一头乘坐某辆大巴的奶牛到达的时候，这辆大巴就可以发车了。 Farmer John 想要做一个优秀的主办者，所以并不想让奶牛们在机场等待过长的时间。

​ 如果 Farmer John 合理地协调这些大巴，等待时间最长的奶牛等待的时间的最小值是多少？

**注：**一头奶牛的等待时间等于她的到达时间与她乘坐的大巴的发车时间之差。

​ 输入保证 $MC\ge N$。

输入格式

​ 输入的第一行包含三个空格分隔的整数 $N$，$M$，和 $C$。第二行包含 $N$ 个空格分隔的整数，表示每头奶牛到达的时间。

输出格式

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

输入输出样例 #1

输入 #1

6 3 2
1 1 10 14 4 3

输出 #1

4

说明/提示

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