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