2886 - 体育比赛

题目描述

学校要举办一场大型体育比赛,参赛选手的身高各不相同。为了保证比赛的公平性,组委会决定将选手分成两组,每组选手的身高差异不能太大。

具体来说,如果两位选手的身高差不超过 K,那么他们可以被分到同一个组中。现在,组委会希望知道最多能选出有多少位选手参与比赛,并且他们的身高差异在各自组内都不超过 K

输入

第一行包含两个整数 NK,其中 N 表示选手的数量,K 表示组内允许的最大身高差。

接下来的 N 行每行包含一个整数,表示每位选手的身高。

输出

输出一个整数,表示最多有多少位选手可以被选到这两个组中。

样例

输入

7 10
180
175
160
190
170
165
195

输出

5

输入

8 20
123
145
180
172
196
188
200
198

输出

6

输入

10 30
150
168
155
207
210
178
189
193
199
198

输出

10
说明

样例 1 解释

将身高为 160 165 170 三位选手分到一组。

将身高为 190 195 的两位选手分到另一组。

是样例 1 的最优解之一的分组方案。

数据范围

对于 10\% 的数据,满足 K = 0

对于另外 20\% 的数据,满足 1 \le N \le 2000K \le 500

对于 100\% 的数据,满足 1 \le N \le 500000 \le K \le 10^9,每个选手的身高都在 [1, 10^9] 的范围内。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题