宝藏猎人
题号:NC232853
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

在S群岛有30001座小岛,它们排列在一条直线上,编号从西到东为0到30000。在这些岛上一共有n个宝石,其中第i个在编号为p_i的岛上。

小K在编号为0的岛上,他想利用他强大的弹跳能力,按以下规则不断向东跳:

首先,他会从0跳到d
之后,他会按下述规则跳:设上一次小K从prev跳到cur,令,下一次他将向东跳到的其中一个岛(若存在)。他跳的距离必须是正整数,即当时他跳的长度不能为0。若没有符合条件的目的地,他将停止向东跳。

小K会在向东跳的同时收集岛上的宝石。求出小K最多能收集多少宝石。

输入描述:

第一行输入两个整数n,d (),表示宝石的数量和小K第一次跳的距离。
接下来的n行,每行一个整数。第i行的数p_i ()表示第i个宝石所在的岛的编号。

输出描述:

输出一个整数,表示小K能收集的宝石的最大数量。
示例1

输入

复制
4 10
10
21
27
27

输出

复制
3

说明

路径为:0 -> 10 (+1) -> 19 -> 27 (+2) ->...
示例2

输入

复制
8 8
9
19
28
36
45
55
66
78

输出

复制
6

说明

路径为:0 -> 8 -> 15 -> 21 -> 28 (+1) -> 36 (+1) -> 45 (+1) -> 55 (+1) -> 66 (+1) -> 78 (+1) ->...
示例3

输入

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

输出

复制
4

说明

路径为:0 -> 7 -> 13 -> 18 (+1) -> 24 (+2) -> 30 (+1) ->...