Bạn là một con kiến, nhưng không phải con kiến bình thường – bạn là con kiến bị ám ảnh bởi phô mai học!

Bạn đã phát hiện một lát phô mai mới trong bếp và muốn gửi càng nhiều tay sai càng tốt để khám phá nó. Hãy tưởng tượng miếng phô mai như một bảng có \(N\) hàng và \(M\) cột, trong đó các hàng được đánh số từ \(1\) đến \(N\) từ trên xuống dưới, và các cột được đánh số từ \(1\) đến \(M\) từ trái sang phải. Một số ô chứa lỗ, trong khi những ô khác chứa phô mai. Chúng ta sẽ ký hiệu ô ở hàng thứ \(r\) và cột thứ \(s\) là \((r, s)\). Ô trên cùng bên trái và dưới cùng bên phải chắc chắn sẽ chứa phô mai.

Hãy ký hiệu số lượng tay sai là \(K\). Các tay sai của bạn sẽ bắt đầu khám phá ở ô trên cùng bên trái và kết thúc ở ô dưới cùng bên phải. Họ chỉ có thể di chuyển xuống dưới và sang phải. Ngoài ra, đường đi của họ không được "giao nhau", nghĩa là chúng ta có thể gán nhãn từ \(1\) đến \(K\) cho họ sao cho không có ô nào mà từ đó một tay sai có nhãn thấp hơn đi ra bên phải, và một tay sai có nhãn cao hơn đi xuống dưới.

Hơn nữa, bạn muốn những đường đi này "khác nhau" theo một nghĩa nào đó, nghĩa là với mọi hai tay sai, tồn tại một ô \((r, s)\) chứa lỗ, sao cho một trong số họ đã ở một thời điểm nào đó ở cột s và ở hàng có nhãn thấp hơn r, trong khi người kia ở một thời điểm nào đó (không nhất thiết đồng thời) ở cột \(s\) và ở hàng có nhãn cao hơn \(r\). Nói một cách không chính thức, mọi cặp tay sai đã tiếp cận một lỗ nào đó từ các phía khác nhau.

Xuất giá trị lớn nhất của \(K\) sao cho tồn tại một lựa chọn đường đi của tay sai thỏa mãn các điều kiện đã cho.

Một số ví dụ về đường đi không thỏa mãn điều kiện: (a) Lựa chọn đường đi không hợp lệ - chúng giao nhau (b) Lựa chọn đường đi không hợp lệ - chúng tiếp cận lỗ từ cùng một phía

Dữ liệu vào

• Dòng đầu tiên chứa các số nguyên dương \(N, M\).
• \(N\) dòng tiếp theo chứa mô tả các hàng của bảng. Dòng thứ \(i\) chứa \(M\) ký tự, trong đó . biểu thị phô mai và # biểu thị ô chứa lỗ.

Dữ liệu ra

• Xuất giá trị lớn nhất có thể của số \(K\) trên một dòng duy nhất.

Chấm điểm

Trong tất cả các subtask, \(2 \le N, M \le 2000\).

Input 1

5 5
.....
.#...
.....
...#.
.....

Output 1

3

Input 2

5 5
....#
....#
.....
.....
#....

Output 2

1

Input 3

.#
#.
..

Output 3

0

Giải thích ví dụ đầu tiên và thứ hai: (a) Ví dụ đường đi cho mẫu đầu tiên (b) Ví dụ đường đi cho mẫu thứ hai