#U1819DS1. Convention

Convention

一场别开生面的牛吃草大会就要在Farmer John的农场举办了!世界各地的奶牛将会到达当地的机场,前来参会并且吃草。具体地说,有N头奶牛到达了机场(1≤N≤105^5),其中奶牛i在时间ti0ti109t_i(0≤t_i≤10^9)到达。Farmer John安排了M(1≤M≤105^5)辆大巴来机场接这些奶牛。每辆大巴可以乘坐C头奶牛(1≤C≤N)。Farmer John正在机场等待奶牛们到来,并且准备安排到达的奶牛们乘坐大巴。当最后一头乘坐某辆大巴的奶牛到达的时候,这辆大巴就可以发车了。Farmer John想要做一个优秀的主办者,所以并不想让奶牛们在机场等待过长的时间。如果Farmer John合理地协调这些大巴,等待时间最长的奶牛等待的时间的最小值是多少?一头奶牛的等待时间等于她的到达时间与她乘坐的大巴的发车时间之差。

输入保证MC≥N。

输入格式(文件名:convention.in):

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

输出格式(文件名:convention.out):

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

输入样例:

6 3 2
1 1 10 14 4 3

输出样例:

4

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