Trong chiến dịch Điện Biên Phủ pháo binh của chúng ta đã lập nên chiến tích phi thường bắn phá chính xác các lô cốt, hầm ngầm của địch tạo điều kiện cho bộ binh xung phong làm chủ trận địa. Trận địa của địch được mô phỏng là những lô cốt đặt tại các vị trí trên một lưới ô vuông kích thước MxN. Thông tin trinh sát đã cho biết giữa hai lô cốt chung cạnh đều có các đường hầm lớn, còn giữa hai lô cốt chung đỉnh có các đường hầm nhỏ kết nối. Đặc thù công phá của pháo binh ta như sau:

(a) Nếu bắn một quả đạn pháo rơi trúng một lô cốt thì nó sẽ tiêu diệt lô cốt này đồng thời sẽ làm nổ tung tất cả các lô cốt được kết nối liên thông với lô cốt này bằng các đường hầm lớn.

(b) Nếu ta bắng đồng thời một chùm 2 quả đạn pháo trúng một lô cốt thì nó sẽ có sức công phá mãnh liệt tiêu diệt lô cốt này cùng với toàn bộ các lô cốt khác có kết nối liên thông bằng đường hầm lớn và nhỏ với lô cốt này.

Chú ý rằng đạn pháo  buộc phải trúng vào vị trí của lô cốt chưa bị tiêu diệt mới phát huy tác dụng. Ví dụ trong sơ đồ dưới đây, nếu pháo ta bắn trúng vị trí có dấu sao (*) thì sẽ tiêu diệt các lô cốt với dấu x in đậm trong trường hợp bắn một quả đạn (a) và hai quả đạn pháo (b).

Các ô vuông trên lưới được đánh địa chỉ (i, j) với chỉ số hàng i, chỉ số cột j. Vị trí trái trên là (1, 1), vị trí phải dưới là (M, N).

Yêu cầu: Nhiệm vụ của bạn là giúp pháo binh ta sử dụng tiết kiệm đạn nhất mà vẫn tiêu diệt toàn bộ các lô cốt trên trận địa của địch.

Dữ liệu: 

• Dòng đầu tiên ghi 2 số tự nhiên M, N cách nhau bởi dấu cách (M, N ≤ 100)
• M dòng tiếp theo, mỗi dòng là N số 0 hoặc 1. Dòng thứ I mô tả trận địa địch tại hàng I, vị trí J trên hàng này mô tả ô vuông với địa chỉ (I, J), số 1 xác định vị trí này có lô cốt.

Kết quả: ghi số tự nhiên K là số đạn tối thiểu cần bắn để tiêu diệt toàn bộ lô cốt của địch trên trận địa.