学校组织研学活动,老师要把同学们分成若干个三人小队。第 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 个小队。