미로탈출

지원이는 n*m크기의 미로에 같히고 말았다.

현재 지원이의 위치는 (1,1)이며, 탈출하려면 (n,m)으로 가야한다.

지원이는 다음의 행동 중 하나를 할 수 있다.

1. 상하좌우로 1칸이동한다. 시간이 1 걸리며 벽으로는 갈 수 없다.
2. 부스터를 써서 벽 1칸을 뚫고 2번째 바로 앞에서 멈춘다. 시간은 1 걸리며 멈출 수 없다.

미로 밖에는 시공의 폭풍이 불고 있다.
따라서 지원이는 미로 밖으로 나가지 않고 가장 빨리 (n,m)으로 가는데 걸리는 시간을 구하려고 한다.

미로 밖은 1칸의 벽으로 둘러쌓여있으며 부스터로 벽을 뚫고 지나가도 지금 지원이의 위치를 제외하고 벽은 재생된다.

input
미로의 크기인 n m이 입력된다.(1<=n,m<=1000)
아래로 n줄에 걸쳐서 m개의 정수가 입력된다.

길은 0, 벽은 1로 표시된다.

output

출발지부터 도착지까지 걸리는 최소시간을 출력하라


ex1

3 2
0 0
0 0
0 0

답 3

ex2

3 3
0 1 0
0 0 1
0 0 0

답 2

ex3

3 3
0 0 1
0 0 0
0 0 0

답 3