241936 - 研学分队

题目描述

学校组织研学活动,老师要把同学们分成若干个三人小队。第 i 名同学有一个能力值 a_i。一个三人小队是合适的,当且仅当队内最高能力值和最低能力值的差不超过 d。每名同学最多参加一个小队,也可以不参加任何小队。请计算最多可以组成多少个合适的三人小队。

输入

第一行两个整数 n, d。第二行 n 个整数,表示每名同学的能力值。

输出

一行一个整数,表示最多可以组成的小队数量。

样例

输入

10 3
12 1 9 4 8 13 2 15 7 3

输出

3
说明

【数据范围】
30 分:1 ≤ n ≤ 18
60 分:1 ≤ n ≤ 5000
100 分:1 ≤ n ≤ 200000,0 ≤ d ≤ 1000000000,1 ≤ a_i ≤ 1000000000
【样例说明】
排序后可以组成 (1, 2, 3)、(7, 8, 9)、(12, 13, 15),所以最多可以组成 3 个小队。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 2 枚
难度 入门


上一题 下一题