Крис е върла планинарка, докато Ели, бидейки кифла, не е. След дълги увещания, най-накрая Ели се съгласи да отидат!

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

Разстоянието между две клетки с координати (R₁, C₁) и (R₂, C₂) е Манхатъновото разстояние между тях: |R₁ – R₂| + |C₁ – C₂|. Така, например, разстоянието между (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 цели числа A_ij, указващи надморската височина на всяка от клетките. На стандартния изход изведете едно цяло число - максималния брой дни, които може да продължи тяхното планинарстване.

• 1 ≤ N, M, D ≤ 500
• 1 ≤ A_ij ≤ 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