Острова Шусеки — это архипелаг из 30001 маленького острова в море Ютампо. Острова располагаются на одной прямой через равные интервалы и пронумерованы от 0 до 30000 с запада на восток. Известно, что на этих островах зарыто много сокровищ. Всего на островах Шусеки находится n драгоценных камней, i-й камень расположен на острове pi.
Мистер Китаюта только что прибыл на остров 0. Будучи отличным прыгуном, он совершит несколько прыжков между островами на восток согласно следующему процессу:
Мистер Китаюта собирает камни на островах, которые он посещает в процессе. Найдите максимальное количество камней, которые он может собрать.
В первой следуют два целых числа через пробел, n и d (1 ≤ n, d ≤ 30 000), обозначающих количество драгоценных камней на островах Шусеки и длину первого прыжка мистера Китаюта, соответственно.
В следующих n строках следуют расположения драгоценных камней. В i-й из них (1 ≤ i ≤ n) записано целое число pi (d ≤ p1 ≤ p2 ≤ ... ≤ pn ≤ 30 000), обозначающее номер острова, содержащего i-й драгоценный камень.
Выведите максимальное количество драгоценных камней, которые может собрать мистер Китаюта.
В первом примере оптимальный маршрут: 0 → 10 (+1 камень) → 19 → 27 (+2 камня) → ...
Во втором примере оптимальный маршрут: 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 камень) → ...
4 10 10 21 27 27
3
8 8 9 19 28 36 45 55 66 78
6
13 7 8 8 9 16 17 17 18 21 23 24 24 26 30
4
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач