题目描述

勇者从家 $(1,1)$ 出发，前往藏宝点 $(n,m)$ 夺取宝藏。地图是一个 $n \times m$ 的二维平面，每个格子都有一个值 $a_{i,j}$，表示经过该格子会遇到的魔兽的等级（等级为 $0$ 表示没有魔兽）。保证起点 $(1,1)$ 的魔兽等级为 $0$。

勇者有一个初始等级（需在出发前确定），以及体力值 $k$。每次移动可以走到上下左右四个方向相邻的格子，不能越界，每次移动消耗 $1$ 点体力。若勇者的等级 $\ge$ 当前格子魔兽的等级，则能安全通过；否则会有生命危险，不允许这样走。

现在，勇者希望在体力耗尽前安全到达藏宝点 $(n,m)$。问在出发前，他至少需要将等级提升到多少级。

输入格式

第一行包含三个整数 $n, m, k$，表示地图的行数、列数和勇者的体力值。

接下来 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$，即该格子的魔兽等级。

输出格式

输出一个整数，表示勇者出发前至少需要提升到的等级。如果无法安全到达，输出 $-1$。

样例

3 3 4
0 3 4
2 5 3
1 2 0

2

样例解释

一条可行的路径：$(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)$，移动步数为 $4$，消耗体力 $4$，路径上的魔兽等级依次为 $0,2,1,2,0$，最大值为 $2$。可以验证不存在最大等级更小的安全路径，因此至少需要达到 $2$ 级。

数据范围

对于 $20\%$ 的数据，$1 \le n,m \le 10$，$0 \le k \le 20$，$0 \le a_{i,j} \le 1000$。

对于 $40\%$ 的数据，$1 \le n,m \le 100$，$0 \le k \le 10^4$，$0 \le a_{i,j} \le 1000$。

对于 $100\%$ 的数据，$1 \le n,m \le 500$，$0 \le k \le 10^5$，$0 \le a_{i,j} \le 10^9$，保证 $a_{1,1}=0$。

注意：体力值 $k$ 可能为 $0$，此时若终点即为起点则可到达，否则不可到达。