题目描述

Kris 是一位非常热衷于爬山的人，而 Eli 则并不是。经过长时间劝说后，Eli 终于同意和她一起去爬山。

她们有一张矩形山地图，共有 N 行 M 列。地图中的每个格子对应一个整数 A[i][j]，表示该位置的海拔高度。

两人计划进行若干天的徒步旅行，并且每天的终点都必须严格高于当天的起点。我们认为她们是从一个格子移动到另一个格子，且这两个格子不要求相邻。

坐标分别为 (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。

注意，在计算距离时，不考虑海拔差。

Eli 不喜欢走太远，因此要求她们在任意一天中移动的距离都不能超过 D。

现在 Kris 想找到一个持续天数尽可能多的路线，也就是一个尽可能长的格子序列，使得：

• 对应海拔严格递增；
• 相邻两个格子之间的距离不超过 D。

请编写程序 TheClimb，帮助她解决这个问题。

输入格式

第一行包含三个整数 N、M 和 D，分别表示地图的行数、列数，以及她们一天内最多能走的距离。
接下来 N 行，每行包含 M 个整数 A[i][j]，表示每个格子的海拔高度。

输出格式

输出一个整数，表示她们最多能持续徒步的天数。

数据范围

• 1 <= N, M, D <= 500
• 1 <= A[i][j] <= 1 000 000

评分说明

测试点按 每组 5 个测试 进行分组。只有当一整组中的所有测试全部通过时，才能获得该组对应分数。

样例

输入

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