C. Ноён Китаюта ба нууц эрдэнэс

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Шүсэкийн олтриг гэдэг нь Ютампо тэнгист байрлах $30001$ жижиг арлуудыг арлуудыг хэлнэ. Арлууд шулууны дагуу ижил зайтай байрлах ба баруунаас зүүн рүү $0$-ээс $30000$ хүртэл дугаарлагджээ. Эдгээр арлууд эрдэнэсээр баян гэдгээрээ алдартай. Шүсэкийн арлууд нийт $n$ эрдэнэстэй ба $i$ дүгээр эрдэнэс $p_{i}$ дүгээр аралд байрлана.

Ноён Китаюта $0$ дүгээр аралд ирчихээд байгаа аж. Тэрээр гайхамшигтай үсрэх чадвараараа арлуудын хооронд зүүн тийш дараахь байдлаар үсрэнэ:

  • Эхлээд тэрээр $0$ дүгээр арлаас $d$ дүгээр арал руу харайна.
  • Тэгээд дараахь дүрмээр үргэлжлүүлэн харайна. $l$-ээр өмнөх харайлтын уртыг тэмдэглэе. Өөрөөр хэлбэл өмнөх харайлт нь $prev$ арлаас $cur$ аралруу харайсан гэж үзвэл $l = cur - prev$ байх юм. Тэрээр $l-1$ эсвэл $l$ эсвэл $l+1$ уртаар зүүн тийш харайна. Өөрөөр хэлбэл $(cur+l-1)$, $(cur+l)$, $(cur+l+1)$ арлуудын аль ч боломжтой руу нь үсэрч болох юм. Харайлтын урт эерэг байх ёстой. Тиймээс $l=1$ үед $0$ уртаар харайж болохгүй юм. Тэрээр ямар ч боломжит харайлт үлдээгүй үед зогсоно.

Ноён Китаюта очсон арал бүрийнхээ эрдэнэсийг цуглуулна. Түүний цуглуулж чадах хамгийн их эрдэнэсийн тоог олоорой.

Оролт

Эхний мөрөнд харгалзан Шүсэкийн арлууд дээрх эрдэнэсийн тоо ба ноён Китаютагийн эхний харайлтын урт болох $n$ ба $d$ ($1 ≤ n, d ≤ 30000$) гэсэн бүхэл тоонууд зайгаар тусгаарлагдан байрлана.

Дараагийн $n$ мөрөнд эрдэнэсүүдийн байршлыг илэрхийлнэ. $i$ ($1 ≤ i ≤ n$) дэх мөрөнд $i$ дэх эрдэнэс байрлах арлын дугаар болох $p_{i}$ ($d ≤ p_{1} ≤ p_{2} ≤ ... ≤ p_{n} ≤ 30000$) гэсэн бүхэл тоо байна.

Гаралт

Ноён Китаютагийн цуглуулж чадах хамгийн их эрдэнэсийн тоог хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
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$ эрдэнэс) → ...

Сэтгэгдлүүдийг ачааллаж байна...