The Climb
Национална Олимпиада по Информатика 2019, Кръг 3
Time Limit: 3s, Memory Limit: 64MiB
Крис е върла планинарка, докато Ели, бидейки кифла, не е. След дълги увещания, най-накрая Ели се съгласи да отидат!

Момичетата имат правоъгълна карта на планината с N реда и M колони. Всяка клетка от картата задава едно цяло число Aij - надморската височина на частта от планината в тази клетката. Момичетата са решили да правят преходи от по един ден, като всеки ден крайната им дестинация е строго по-висока (на по-голяма надморска височина) от тази, от която тръгват в съответния ден. Ще считаме, че те се движат от клетка в клетка, като клетките не е задължително да са съседни.

Разстоянието между две клетки с координати (R1, C1) и (R2, C2) е Манхатъновото разстояние между тях: |R1 – R2| + |C1 – C2|. Така, например, разстоянието между (3, 2) и (5, 8) е 2 + 6 = 8; разстоянието между (5, 5) и (1, 2) е 4 + 3 = 7; а разстоянието между (8, 22) и (13, 7) е 5 + 15 = 20. Забележете, че денивелацията (разликата във височината на клетките) бива игнорирана при изчисляването на разстоянието.

Ели не обича да ходи твърде много, затова наложи ограничение в никой от дните да не изминават по-голямо разстояние от D.

Сега Крис се опитва да намери маршрут с възможно най-много дни - тоест възможно най-дълга последователност от клетки, такива, че надморските им височини да са строго нарастващи и разстоянието между последователни такива да е не по-голямо от D. Помогнете на момичето с тази задача!
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, M, и D - съответно броя редове и колони на картата, както и максималното разстояние, което момичетата могат да изминат на ден. На следващите N реда ще бъдат зададени по M цели числа Aij, указващи надморската височина на всяка от клетките.
Изход
На стандартния изход изведете едно цяло число - максималния брой дни, които може да продължи тяхното планинарстване.
Ограничения
  • 1 ≤ N, M, D ≤ 500
  • 1 ≤ Aij ≤ 1,000,000
Примерен Вход Примерен Изход
4 5 3 39 13 26 20 17 37 17 14 22 24 42 12 10 21 33 18 20 13 19 31 15
Оптималният път би бил през клетките с височини: 10 → 12 → 13 (което и да е) → 14 → 17 (в (2, 2)) → 18 → 19 → 20 (което и да е) → 21 → 22 → 24 → 26 → 37 → 39 → 42
Мрън!