Cho ma trận nhị phân \(A\) gồm \(n\) dòng và \(m\) cột. Mỗi bước đi, bạn có thể di chuyển từ một ô đến một trong bốn ô kề cạnh. Bạn không được đi vào ô có số \(1\).

Tìm đường đi ngắn nhất từ \((1,1)\) đến \((n,m)\).

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• \(n\) dòng tiếp theo, mỗi dòng gồm một xâu nhị phân độ dài \(m\), thể hiện ma trận \(A\).

Output

• In ra độ dài đường đi ngắn nhất từ \((1,1)\) đến \((n,m)\) hoặc in ra \(-1\) nếu không tồn tại đường đi nào.

Điều kiện

• \(1 \le n,m \le 10^3\)

Sample Input 1

4 5
01000
01010
00010
11010

Sample Output 1

11