文件输入输出提示

本题采用文件输入输出。提交代码时，请在 main 函数开头加入文件重定向，并从 shuttle.in 读入、输出到 shuttle.out。

freopen("shuttle.in", "r", stdin);
freopen("shuttle.out", "w", stdout);

题目描述

苗苗负责安排杯赛接驳车，把同学们从校门送到活动楼。

共有 $n$ 名同学到达校门，第 $i$ 名同学到达的时间为 $a_i$。学校最多可以安排 $m$ 辆接驳车，每辆车最多乘坐 $c$ 名同学，每辆车只发车一次。

一辆车可以接若干名同学。它必须等到车上所有同学都到达后才能出发。

如果一辆车上最早到达的同学时间为 $x$，最晚到达的同学时间为 $y$，那么这辆车上等待最久的同学等待了 $y-x$ 分钟。

请合理安排每名同学乘坐哪一辆车，使所有同学都能被送走。请输出在最优安排下，“所有同学中的最大等待时间”的最小值。

输入格式

从文件 shuttle.in 中读入数据。

第一行输入三个整数 $n,m,c$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每名同学到达校门的时间。输入的到达时间不一定有序。

输出格式

输出到文件 shuttle.out 中。

输出一行一个整数，表示最小可能的最大等待时间。

输入输出样例 #1

输入 #1

7 3 3
1 2 3 10 11 14 20

输出 #1

4

说明/提示

一种最优安排为：

• 第一辆车接到达时间为 $1,2,3$ 的同学，最大等待时间为 $3-1=2$；
• 第二辆车接到达时间为 $10,11,14$ 的同学，最大等待时间为 $14-10=4$；
• 第三辆车接到达时间为 $20$ 的同学，最大等待时间为 $0$。

因此最大等待时间为 4。可以证明不可能让最大等待时间小于 4。

输入输出样例 #2

输入 #2

5 2 4
8 8 8 8 8

输出 #2

0

数据范围与子任务

对于所有数据，满足：

• $1\le n\le 2\times 10^5$；
• $1\le m\le n$；
• $1\le c\le n$；
• $m\times c\ge n$；
• $0\le a_i\le 10^9$。

shuttle_大样例.zip