Devil City Jump

In a rectangular grid divided into \(N \times M\) square rooms, each room carries a magic number (a natural number from 1 to 13) written on its wall. An explorer enters the maze at \((1,1)\) and must exit at \((N,M)\) by making a series of jumps under the following rules:

• At each room, the explorer observes its magic number \(X\). He may choose one of the eight directions (vertical, horizontal, or diagonal), and then jump exactly \(X\) rooms in that direction. However, the entire consecutive sequence of \(X\) rooms in the chosen direction must lie within the grid; otherwise, he cannot jump in that direction.
• The explorer is not allowed to make two consecutive jumps in the same direction.

Your task is to determine the minimum number of jumps required for the explorer to reach the exit. If it is impossible for the explorer to reach \((N,M)\), output \(-1\).

inputFormat

The first line contains two integers \(N\) and \(M\), the number of rows and columns of the grid. Each of the following \(N\) lines contains \(M\) integers representing the magic numbers in the corresponding rooms.

outputFormat

Output a single integer representing the minimum number of jumps needed to travel from \((1,1)\) to \((N,M)\). If it is impossible, output \(-1\).

sample

3 3
2 2 1
2 1 1
3 1 1

1