Problem Description

After eating too much fruit in Farmer John's kitchen, Bessie the cow is getting some very strange dreams! In her most recent dream, she is trapped in a maze in the shape of an N × M grid of tiles (1 ≤ N, M ≤ 1,000). She starts on the top-left tile and wants to get to the bottom-right tile. When she is standing on a tile, she can potentially move to the adjacent tiles in any of the four cardinal directions.

But wait! Each tile has a color, and each color has a different property! Bessie's head hurts just thinking about it:

(If you're confused about purple tiles, the example will illustrate their use.)

Please help Bessie get from the top-left to the bottom-right in as few moves as possible.


The first line has two integers N and M, representing the number of rows and columns of the maze.

The next N lines have M integers each, representing the maze:

The top-left and bottom-right integers will always be 1.


A single integer, representing the minimum number of moves Bessie must use to cross the maze, or -1 if it is impossible to do so.

Sample Input

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

Sample Output



In this example, Bessie walks one square down and two squares to the right (and then slides one more square to the right). She walks one square up, one square left, and one square down (sliding two more squares down) and finishes by walking one more square right. This is a total of 10 moves (DRRRULDDDR).