Input

The first line contains two integers: the length MM, and the width NN of the vault, satisfying 1 \leq M,N \leq 10001≤M,N≤1000.The following MM lines each contain NN integers. Each integer specifies the height of the pile of coins in the vault at the corresponding position. (The first line describes the north-most stacks from west to east; the last line describes the south-most stacks from west to east). The heights are given in meters and all heights are at least 00 and at most 10^9109 (yes, your friend’s uncle is very rich).

Output

Output a single line containing a single integer: the length in meters of the shortest ladder that allows you to get from the north west corner to the south east corner.

#### # 样例输入 1

3 3
1 2 3
6 5 4
7 8 9


#### # 样例输出 1

1


#### # 样例输入 2

1 4
4 3 2 1


#### # 样例输出 2

0


#### # 样例输入 3

7 5
10 11 12 13 14
11 20 16 17 16
12 10 18 21 24
14 10 14 14 22
16 18 20 20 25
25 24 22 10 25
26 27 28 21 25


#### # 样例输出 3

3