修石群岛是由 30001 个小岛组成的位于 Yutampo 海的群岛。岛屿沿一条线均匀分布,从西向东编号为0至30000个。众所周知,这些岛屿蕴藏着许多宝藏。修石群岛一共有n颗宝石,第i颗宝石位于pi岛。
北裕太先生刚刚到达0号岛,凭借他出色的跳跃能力,他会按照以下流程反复在东边的岛屿之间进行跳跃:
- 首先,他将从0号岛跳到d岛。
- 之后,他将按照以下规则继续跳跃。令l为上一次跳跃的长度,即如果他的上一次跳跃是从island prev到island cur,则令l = cur - prev。他将向东进行长度为 l - 1、l 或 l + 1 的跳跃。也就是说,他会跳到岛 (cur + l - 1)、(cur + l) 或 (cur + l + 1)(如果存在的话)。跳跃的长度必须为正数,即当l = 1时他不能进行长度为0的跳跃,如果没有有效的目的地,他就会停止跳跃。
Kitayuta先生将收集在此过程中访问的岛屿上的宝石。找出他可以收集的最大宝石数量。
输入
输入的第一行包含两个空格分隔的整数 n 和 d (1 ≤ n, d ≤ 30000),分别表示修石群岛中宝石的数量和 Kitayuta 先生第一次跳跃的长度。
接下来的 n 行描述了宝石的位置。其中第 i 个 (1 ≤ i ≤ n) 包含一个整数 pi (d ≤ p1 ≤ p2 ≤ ... ≤ pn ≤ 30000),表示包含第 i 颗宝石的岛屿的编号。
输出
打印Kitayuta先生可以收集的最大宝石数量。
示例
输入 #1
4 10 10 21 27 27
输出 #1
3
输入 #2
8 8 9 19 28 36 45 55 66 78
输出 #2
6
输入 #3
13 7 8 8 9 16 17 17 18 21 23 24 24 26 30
输出 #3
4
注意
在第一个示例中,最佳路线是 0 → 10 (+1 gem) → 19 → 27 (+2 gem) → ...
在第二个样本中,最佳路线是0→8→15→21→28(+1宝石)→36(+1宝石)→45(+1宝石)→55(+1宝石)→66(+1宝石)→78(+1宝石)→...
在第三个样本中,最佳路线是0→7→13→18(+1宝石)→24(+2宝石)→30(+1宝石)→...