Luka có một thanh sô-cô-la gồm \(n\) hàng và \(m\) cột, mỗi ô là sô-cô-la trắng hoặc đen. Luka chỉ muốn ăn phần đen. Trước khi ăn, cậu có thể cắt dọc giữa hai cột, từ mép trên đến mép dưới của thanh, và/hoặc cắt ngang giữa hai hàng, từ mép trái đến mép phải. Sau các lần cắt, các mảnh đều là hình chữ nhật. Hãy tìm số nhát cắt ít nhất để mỗi mảnh chỉ gồm một màu sô-cô-la.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,m\) (\(1\le n,m\le200\)), là số hàng và số cột. Mỗi trong \(n\) dòng tiếp theo chứa \(m\) ký tự 0 hoặc 1: 0 là ô trắng, 1 là ô đen.

Dữ liệu ra

In số nhát cắt nhỏ nhất cần thực hiện.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(5\) điểm: thanh sô-cô-la là bàn cờ; ô hàng \(i\), cột \(j\) màu trắng khi \(i+j\) chẵn và màu đen khi \(i+j\) lẻ.
2. \(11\) điểm: \(n=1\).
3. \(11\) điểm: đúng một ô có màu đen.
4. \(23\) điểm: không có ràng buộc thêm.

Ví dụ

4 7
0000000
0111000
0111100
0000000

6

4 5
00000
01100
01100
00000

4

4 4
0101
1010
0101
1010

6

Nguồn

COCI 2025/2026 - Vòng 6, bài Čokolada.

Đề bài và dữ liệu kiểm thử được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.