You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个N*M大小的迷宫矩阵，迷宫的每一个格子有一个数值（a[i][j] <10^9）。小码君在迷宫中发现，它只能朝着上下左右四个方向的相邻格子前进，并且只能进入比当前位置数值更大的格子。但是小码君有个紧急呼救按钮，他可以通过按下按钮，强行进入到不满足数值大小要求的相邻格子，可惜这个按钮只能按K次。请问小码君从这个迷宫任选一个格子出发，在紧急呼救按钮的帮助下，最多能走多少步（开始位置计入步数，即站在起点是步数为1）。

输入格式

第一行输入三个数N, M, K。接下来N行，每行M个数，表示迷宫中每个格子的值。 1 ≤ N ≤ 500 1 ≤ M ≤ 500 0 ≤ K ≤ 10

输出格式

输出小码君在迷宫中能走的最大步数

样例 #1

样例输入 #1

3 3 1
1 3 3
2 4 9
8 9 2

样例输出 #1

6

提示

其中一种行走方案： (0, 0) -> (0, 1) -> (0, 0) -> (1, 0) -> (2, 0) -> (2, 1)