题目描述

在育华学校的劳动节活动中，同学们参与了一场特别的二维跳房子游戏。游戏场地是一个 $n \times m$ 的网格，每个格子代表一个房子，坐标从 $(1, 1)$ 到 $(n, m)$。每个房子 $(i, j)$ 都有一个特殊的规则，玩家站在这个房子上时，可以选择向上下左右四个方向跳 $t_{ij}$ 步。

游戏的目标是玩家从左上角的房子 $(1, 1)$ 出发，跳到右下角的房子 $(n, m)$。请你计算玩家完成这个目标最少需要跳多少步。如果无论如何都无法跳到 $(n, m)$，输出 -1。需要注意的是，玩家在跳跃过程中不能跳出网格的边界（即跳跃后的坐标 $(x, y)$ 必须满足 $1 \leq x \leq n$ 且 $1 \leq y \leq m$）。

输入格式

第一行包含两个正整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$），分别表示网格的行数和列数。 接下来 $n$ 行，每行包含 $m$ 个正整数 $t_{ij}$（$1 \leq t_{ij} \leq \max(n, m)$），表示站在房子 $(i, j)$ 上时可以向四个方向跳跃的步数。

输出格式

输出一个整数，表示从房子 $(1, 1)$ 跳到房子 $(n, m)$ 最少需要的步数。如果无法到达，输出 -1。

样例

• 输入

3 3
2 1 1
1 1 1
1 1 1

• 输出

3