Cho một ma trận ô vuông $N \times M$, mỗi ô trong ma trận được đánh dấu 0 hoặc 1 cho biết ô đó đã có người giẫm qua hay chưa.

Biết rằng một người có thể bắt đầu từ một ô bất kỳ, sau đó mỗi bước chỉ có thể đi sang phải hoặc đi xuống dưới một ô. Sau khi đi một số bước, người đó có thể rời khỏi ma trận. Các ô mà người này đi qua đều được đánh dấu 1, bao gồm cả ô bắt đầu và ô kết thúc. Chú ý ô bắt đầu và ô kết thúc không nhất thiết phải nằm ở mép ma trận.

Hãy tính có ít nhất bao nhiêu người đã đi qua ma trận.

Dữ liệu vào

Dòng đầu tiên của đầu vào chứa hai số nguyên $N$, $M$. $N$ dòng tiếp theo, mỗi dòng chứa một xâu 01 độ dài $M$, biểu diễn ma trận ô vuông.

Dữ liệu ra

In ra một số nguyên biểu thị đáp án.

Ví dụ

Input

5 5
00100
11111
00100
11111
00100

Output

3

Ghi chú

Phạm vi dữ liệu

Với tất cả các test, $1 \leq N, M \leq 20$, số ô được đánh dấu 1 không vượt quá $200$.

Nguồn: Lanqiao Cup 2019 vòng chung kết quốc gia, bảng A bài G (bảng C bài H).