Luka rất thích sô-cô-la. Cậu đang háo hức ăn một thanh sô-cô-la lớn mà cậu nhận được vào dịp sinh nhật, gồm ~n~ hàng và ~m~ cột. Thanh sô-cô-la được tạo bởi các ô sô-cô-la đen và trắng. Tuy nhiên, Luka không thích sô-cô-la trắng lắm và chỉ muốn ăn các ô màu đen.

Trước khi bắt đầu ăn, Luka sẽ cắt thanh sô-cô-la. Cậu được phép thực hiện một số nhát cắt dọc và/hoặc ngang giữa các hàng và các cột.

• Một nhát cắt dọc đi từ mép trên xuống mép dưới của thanh sô-cô-la.
• Một nhát cắt ngang đi từ mép trái sang mép phải của thanh sô-cô-la.

Sau khi cắt xong, Luka sẽ thu được một số miếng hình chữ nhật.

Vì Luka chỉ ăn phần màu đen, cậu muốn tách hoàn toàn các ô đen ra khỏi các ô trắng. Nói cách khác, mỗi miếng thu được phải gồm toàn sô-cô-la đen hoặc toàn sô-cô-la trắng.

Luka muốn bắt đầu ăn càng sớm càng tốt, nên cậu cần biết số nhát cắt ít nhất phải thực hiện để tách riêng phần đen và phần trắng.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~, là số hàng và số cột của thanh sô-cô-la.

Mỗi trong ~n~ dòng tiếp theo chứa ~m~ ký tự, mỗi ký tự là ~0~ hoặc ~1~. Ký tự ~0~ biểu diễn một ô màu trắng, còn ký tự ~1~ biểu diễn một ô màu đen.

Output

In ra trên một dòng duy nhất số nhát cắt nhỏ nhất cần thực hiện để tách riêng các ô đen và các ô trắng.

Ràng buộc

• ~1 \le n, m \le 200~

Chấm điểm

• Subtask 1 (5 điểm): Thanh sô-cô-la là một bàn cờ, tức ô ở hàng ~i~, cột ~j~ có màu trắng nếu ~i+j~ là số chẵn và màu đen nếu ~i+j~ là số lẻ
• Subtask 2 (11 điểm): ~n = 1~
• Subtask 3 (11 điểm): Chỉ có đúng ~1~ ô màu đen
• Subtask 4 (23 điểm): Không có ràng buộc bổ sung.

Sample Input 1

4 7
0000000
0111000
0111100
0000000

Sample Output 1

6

Sample Input 2

4 5
00000
01100
01100
00000

Sample Output 2

4

Sample Input 3

4 4
0101
1010
0101
1010

Sample Output 3

6

Giải thích

• Ví dụ 2: Luka nên cắt giữa hàng ~1~ và ~2~, giữa hàng ~3~ và ~4~, giữa cột ~1~ và ~2~, và giữa cột ~3~ và ~4~.
• Ví dụ 3: Luka phải cắt giữa mọi cặp hàng kề nhau và mọi cặp cột kề nhau, tổng cộng ~6~ nhát cắt.