CSP 大赛

题目描述

2026 年的 CSP 马上就要在全国举办了！四川的各位参赛选手将会到达成都的火车站参赛。总计将会有 N 位同学依次到达车站，其中第 i 名同学在时间 $t_i$到达。珅泽教育的主教练安排了 M辆大巴来车站接同学们。每辆大巴都可以乘坐 K 位同学。

由于比赛马上开始，于是主教练开始安排先到的同学们尽快坐上大巴，避免同学们在车站等待的时间过长。所有 M 辆大巴都已经准备就绪，随时可以发车了！如果主教练能合理地协调这些大巴，他想知道等待时间最长的同学的等待时间最小值是多少。一位同学等待的时间等于他乘坐的大巴的发车时间与他到达的时间之差。

输入描述

输入的第一行包含三个空格分隔的整数 N、M 和 K。

第二行包含 N 个空格分隔的整数，表示每位学生到达的时间。

输出描述

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

样例

输入：

6 3 2
1 1 10 14 4 3

输出：

4

样例解释：两个时间 1 到达的同学乘坐一辆巴士，时间 3 和时间 4 到达的同学乘坐第二辆，时间 10 和时间 14 到达的同学乘坐第三辆，那么等待时间最长的学生等待了 4 个单位时间（时间 10 到达的学生从时间 10 等到了时间 14）。

输入样例 #2

1 1 1
0

输出样例 #2

0

输入样例 #3

5 1 5
0 0 0 0 0

输出样例 #3

0

数据范围

1 ≤ N ≤ 10^5

0 ≤ $t_i$ ≤ 10^9

1 ≤ M ≤ 10^5

1 ≤ K ≤ N

输入保证 N ≤ M×K。