#2040. 公交车与接机

公交车与接机

题目描述

公交车最近要去飞机场接机。

具体地说,有 N\red{N }个客人到达了机场(1\red{1 ≤} N\red{N ≤} 105\red{10^5)},其中客人i\red{i}在时间 ti\red{t_i(}0\red{0 ≤} ti\red{t_i ≤}109\red{10^9)}到 达。公交车安排了 M\red{M(}1\red{1 ≤} M\red{M ≤} 105\red{10^5)}辆大巴来机场接这些客人。每辆大巴可以乘坐 C\red{C }个人( 1\red{1 ≤} C\red{C ≤} N\red{N)}。公交车正在机场等待客人们的到来,并且准备安排到达的客人乘坐大巴。当最后一 头乘坐某辆大巴的客人到达的时候,这辆大巴就可以发车了。公交车想要做一个优秀的接机人,所以 并不想让客人们在机场等待过长的时间。如果公交车合理地协调这些大巴,等待时间最长的客人等待 的时间的最小值是多少?一个客人的等待时间等于他的到达时间与他乘坐的大巴的发车时间之差。 输入保证 MC\red{MC ≥} N\red{N}

输入格式

输入的第一行包含三个空格分隔的整数 N\red{N,}M\red{M,}C\red{C}

第二行包含 N\red{N }个空格分隔的整数,表示每个 客人到达的时间。

输出格式

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

样例

输入样例

6 3 2
1 1 10 14 4 3

输出样例

4

提示

如果两个时间 1\red{1 }到达的客人乘坐一辆巴士,时间 2\red{2 }和时间 4\red{4 }到达的客人乘坐乘坐第二辆,时间 10\red{10 }和 时间 14\red{14 }到达的客人乘坐第三辆,那么等待时间最长的客人等待了 4\red{4 }个单位时间(时间 10\red{10 }到达的客人 从时间 10\red{10 }等到了时间 14\red{14})。

统计

相关

在下列比赛中:

入门班3