Đối với Mirko, không có hạnh phúc nào lớn hơn việc tìm thấy một cuộn băng dính mới, và ngày hôm nay anh ấy đặc biệt hạnh phúc vì anh ấy còn tìm thêm được cuốn lịch Advent của Slavko.

Cuốn lịch Advent có thể biểu diễn như một bảng hình chữ nhật với ~n~ hàng và ~m~ cột, mỗi ô vuông chứa một cửa sổ nhỏ, và đằng sau mỗi cửa sổ là một miếng sô cô la. Slavko đã mở một số ô trong số đó, còn những cửa sổ khác vẫn đang đóng.

Mirko quyết định sử dụng cuộn băng dính của anh ấy để dán lại tất cả những cửa sổ đóng. Cuộn băng dính thì dài vô tận, và nó có chiều rộng bằng ~1~ ô của cuốn lịch. Mirko có thể xé một đoạn băng dính và dùng nó để dán một đoạn liền kề những ô cửa sổ đã đóng theo chiều dọc hoặc chiều ngang. Anh ấy không muốn dán nhiều hơn một lớp băng dính lên bất kì cửa sổ nào, vì anh ấy vẫn muốn giữ tình bạn với Slavko.

Anh ấy đang tự hỏi rằng, anh ấy cần tối thiểu bao nhiêu mẩu băng dính để dán lại hết các cửa sổ đóng trong cuốn lịch.

Input

Dòng dầu tiên chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n \le 1000, 1 \le m \le 10)~, các kích thước của cuốn lịch Advent.

Mỗi dòng trong số ~n~ dòng sau chứa ~m~ kí tự . và # , biểu diễn cuốn lịch Advent.

Kí tự . mô tả một ô cửa sổ mở, và kí tự # biểu diễn một ô cửa sổ đóng

Output

In ra số lượng nhỏ nhất các mẩu băng dính cần thiết để dán hết những ô cửa sổ đóng

Sample 1

Input

2 3
#.#
###

Output

3

Sample 2

Input

4 3
.#.
###
.##
.#.

Output

3

Sample 3

Input

4 4
####
#.#.
#.##
####

Output

5

Giải thích test ví dụ đầu tiên

Một giải pháp có thể đưa ra là sử dụng một đoạn băng dính cho cột đầu tiên, một đoạn cho cột thứ ~3~ và một đoạn cho ô cửa sổ ở hàng thứ ~2~ và cột thứ ~2~

Subtask

Có ~10~ test thỏa mãn: mỗi ô cửa sổ đóng liền kề với tối đa ~2~ ô cửa sổ đóng khác

Có ~8~ test thỏa mãn: ~1 \le n \le 10~

Có ~10~ test còn lại: không có ràng buộc gì thêm