// problem #86

벽 부수고 이동하기

N×M 지도에서 0은 이동 가능, 1은 벽이다. (1,1)에서 (N,M)까지 최단 경로 칸 수를 구하되, 벽을 최대 한 번 부술 수 있다. 도달 불가면 -1.

입력

첫 줄 N, M. 이후 N개 줄에 붙어있는 0/1 문자열.

출력

지나는 최소 칸 수(시작·끝 포함), 불가능 -1.

제한

• 1 ≤ N, M ≤ 1,000

예제

6 4
0100
1110
1000
0000
0111
0000

15

4 4
0111
1111
1111
1110

-1