Codeforces Round 286 (Div. 2) |
---|
Закончено |
Острова Шусеки — это архипелаг из 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-й драгоценный камень.
Выведите максимальное количество драгоценных камней, которые может собрать мистер Китаюта.
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
В первом примере оптимальный маршрут: 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 камень) → ...
Название |
---|