严神设计了一个机器人, 这个机器人可以跳跃。
严神还设计了一个地图, 该地图为为 n \times m 的矩形。 矩形中每个点有高度 height 。 机器人最初在左上角。 移动的规则是:
机器人只能移动到同一行或同一列中高度比当前更高的位置;
机器人最多只能移动到距离为 k 的位置;
机器人不能移动到地图外。
我们知道, 在该地图上, (x1, y1) 与 (x2, y2) 的距离为 |x1 - x2| + |y1 - y2| .
现在严神想知道, 该机器人能够到过的格子中, 高度和最大是多少? 因为严神很忙, 这道题就交给你了。
第 1 行, 三个整数 n , m , k .
接下来 n 行, 每行 m 个整数, 代表地图上每个点的高度。
输出仅一个整数, 机器人能够到过的格子中,最大的高度和。
5 5 1 1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16 21 22 23 24 25
325
3 4 2 1 4 3 2 8 10 7 6 12 11 5 9
57
样例 1 中, 机器人可以走遍所有格子。 样例 2 中, 机器人可以按照路线 1 - 3 - 5 - 7 - 8 - 10 - 11 - 12 走, 得分为57. 可以证明这是最大得分。
本题采用捆绑测试。