Đề bài

Alice vừa tìm thấy một cuộn băng dính mới, và hôm nay cô ấy đặc biệt hạnh phúc vì cô ấy cũng đã tìm thấy lịch Mùa vọng của em gái mình.

Lịch Mùa vọng có thể được biểu diễn dưới dạng một bảng có ~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. Em gái của Alice đã mở một số cửa sổ và những cửa sổ khác vẫn đang đóng.

Alice quyết định dùng băng dính của mình để dán tất cả các cửa sổ đã đóng lại. Đoạn băng dài vô hạn, và nó rộng bằng một ô lịch. Alice có thể xé một đoạn băng và sử dụng nó để dán một số chuỗi ô cửa sổ đóng liền kề theo chiều ngang hoặc chiều dọc. Cô ấy không muốn đặt nhiều hơn một mảnh băng trên cửa sổ nào đó.

Alice đang tự hỏi số lượng mảnh băng tối thiểu mà cô cần để dán tất cả các cửa sổ đã đóng lại là bao nhiêu.

Input

Vào từ file văn bản LICHMUAVONG.INP:

• Dòng đầu tiên chứa các số nguyên ~n~ và ~m~ (~1 \leq n \leq 1000, 1 \leq m \leq 10~), kích thước của lịch Mùa Vọng.
• Mỗi dòng trong số ~n~ dòng sau chứa ~m~ ký tự '.' và '#' đại diện cho lịch Mùa Vọng. Các ký tự '.' biểu thị một cửa sổ đang mở và ký tự '#' biểu thị một cửa sổ đã đóng.

Output

Đưa ra file văn bản LICHMUAVONG.OUT:

• Đưa ra số lượng mảnh băng tối thiểu cần thiết để dán tất cả các cửa sổ đã đóng.

Ví dụ

Sample Input 1

2 3
#.#
###

Sample Output 1

3

Giới hạn

• Thời gian: ~2.0s~
• Bộ nhớ: ~256M~
• Có 35% số test ứng với 35% số điểm của bài có mỗi cửa sổ đã đóng sẽ liền kề với nhiều nhất hai cửa sổ khác đóng.
• Có 30% số test khác ứng với 35% số điểm của bài có ~1 \leq n \leq 10~.
• Có 35% số test khác ứng với 30% số điểm của bài không có ràng buộc thêm.

Ghi chú

Giải thích ví dụ 1: Sử dụng một miếng băng dính cho cột đầu tiên, một miếng cho cột thứ ba và một miếng cho ô ở hàng thứ hai và cột thứ hai.