ami có một bảng hình chữ nhật A có kích thước \(m \times n\). Các hàng được đánh số từ \(1\) đến \(m\), các cột được đánh số từ \(1\) đến \(n\), và ô nằm trên hàng \(i\), cột \(j\) được gọi là ô \(A_{i,j}\). Hiện tại ô \(A_{i,j}\) được tô màu đen hoặc hồng. Một bảng hình chữ nhật bất kỳ được gọi là blink nếu từ ô \((1, 1)\) tồn tại đường đi đến ô \((m, n)\) thoả mãn điều kiện sau:

1. Từ một ô \((i, j)\) chỉ được đi xuống dưới \((i+1, j)\) hoặc qua phải \((i, j+1)\), và không được đi ra ngoài bảng.
2. Tất cả các ô trên đường đi đều là màu hồng.

Các bạn cần biến bảng thành blink bằng cách thực hiện ít lần nhất các thao tác sau: chọn một hình chữ nhật con trong bảng và đổi màu tất cả các ô trong hình chữ nhật đó (đen thành hồng và hồng thành đen).

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(m\) và \(n\) là kích cỡ của bảng.
• \(m\) dòng sau, dòng \(i\) chứa \(n\) kí tự \(a_{i,j}\).
• \(a_{i,j}\) = # biểu thị một ô màu đen và \(a_{i,j}\) = . biểu thị một ô màu hồng.

Output

• Một số nguyên là số thao tác ít nhất.

Example

3 3
.#.
.#.
...

0

2 2
.#
##

1

Giới hạn

• \(100\%\) test có \(1 \leq n, m \leq 100\).