Problem H
Stepping Stones

While hiking, Alice has found herself on the North side of a river and needs to get to the South riverbank. There are rocks distributed in the river along a grid which she can step on. When stepping off a rock of height $H_{i, j}$, Alice must move onto another rock exactly $H_{i, j}$ away. If the South riverbank is $H_{i, j}$ away or less, she can also step onto the South riverbank. If Alice steps onto a rock of height $0$, she will be stuck and cannot move onto another rock. Alice can only step in the North, East, South and West directions. The North riverbank that Alice starts on has a height of $1$, allowing her to step onto any rock adjacent to the North riverbank.

The rocks are laid out in an $N \times M$ grid. Alice starts at the top (North) and wants to make her way to the bottom (South). She cannot step beyond the East or West side of the rock grid. Alice can step off the North riverbank at any column, and can step onto the South riverbank at any column.

What’s the minimum amount of steps that Alice needs to take in order to reach the other side of the river?

Input

The first line of input contains two integers $N$ ($1 \leq N \leq 10^5$) and $M$ ($1 \leq M \leq 10^5$ and $N \times M \leq 10^5$), which are the dimensions of the rock grid.

The next $N$ lines each contain $M$ integers $H_{i, j}$ ($0 \leq H_{i, j} \leq 100$), the heights of the $j$-th rock in the $i$-th row.

Output

Print a single integer, the minimum number of steps Alice needs to reach the other side of the river, or print $-1$ if she cannot reach the other side of the river.

3 8
1 1 1 2 1 3 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

2

9 3
1 4 1
1 1 1
1 7 1
1 1 1
1 2 1
1 1 1
1 1 1
1 1 1
1 1 1

4

3 3
1 1 1
0 0 0
1 1 1

-1