题目描述

∗∗电视台有一档风靡一时的闯关节目，小t曾经也看过这个节目，有一天，他突然想以该题为背景出一道有趣的题…… 给定一个 $n$ 行 $m$ 列的矩阵，每一个点 ( $i$ , $j$ ) (指第 $i$ 行 第 $j$ 列的点)初始状态都是关闭的，在 $a_{i,j}$ 时才会开启，并且不再关闭。你只能前往已经开启的点，起点在( $1$ ，$1$ )，终点( $n$，$m$ )，并且只能移动到相邻的点且不能离开这个矩阵。你的速度非常快，甚至快到可以忽略在相邻点之间移动的时间。小t想知道他最早可以在什么时间通关。

输入格式

一行，输入两个整数 $n$ 和 $m$ ,表示矩阵的行数和列数。 接下来 $n$ 行，每行 $m$ 的数字，表示 $a_{i,j}$ 。

$1 \\leq n , m \\leq 1000$

$1 \\leq a_{i,j} \\leq 10^9$

输出格式

一个数字，表示通关的最早时间。

样例

2 2 
1 10 
5 8

8

5 5 
3 4 5 8 7 
4 8 7 9 2 
9 8 7 6 8 
3 4 5 2 7 
9 4 2 1 3

7

提示

by 励翔