P4712 - 收集宝石

题目

P4712收集宝石

限制 : 时间限制 : 10000 MS 空间限制 : 100000 KB

评测说明 : 1s,96m

问题描述

何老板最近在玩一款收集宝石的手游。游戏虽然简单，但他仍然乐此不疲。
游戏中，有30001个小岛排成一条直线，小岛从左往右编号0到30000，相邻岛屿间距为1。
有n块宝石分布在这些岛上，其中第i块宝石分布在Pi号岛上。
游戏规则如下：
游戏开始时，游戏角色小飞侠位于0号小岛。何老板操控小飞侠往右飞行。
第1次飞行距离只能是d米。也就是第一次飞行只能飞到d号小岛去着陆。
第i(i>1)次飞行的距离可从Len-1, Len, Len+1中任选一个。Len是第i-1次飞行的距离。
如果没法继续往右飞行了，游戏结束。
每着陆到一个岛上，小飞侠就可以收集该岛上的所有宝石。何老板想知道，他最多能获得多少块宝石。

输入格式

第一行，两个整数n和d 1 ≤ n, d ≤ 30000
接下来n行，每行一个整数，其中第i行表示第i块宝石所在的小岛的编号Pi。
1 ≤ i ≤ n
d ≤ P1 ≤ P2 ≤ ... ≤ Pn ≤ 30000

输出格式

一个整数，表示何老板最多能够收集到的宝石数量

样例输入 1

4 10
10
21
27
27

样例输出 1

样例输入 2

8 8
9
19
28
36
45
55
66
78

样例输出 2

样例输入 3

13 7
8
8
9
16
17
17
18
21
23
24
24
26
30

样例输出 3

样例输入 4

11 15
15
18
19
19
21
23
24
26
26
29
30

样例输出 4

提示

样例1说明
飞行路线 0 → 10 (+1 宝石) → 19 → 27 (+2 宝石) → ...
样例3说明
飞行路线 0 → 7 → 13 → 18 (+1 宝石) → 24 (+2 宝石) → 30 (+1 宝石) → ...

数据范围

对于40%的数据: 1 ≤ n, d ≤ 1000
对于100%的数据： 1 ≤ n, d ≤ 30000