Lớp học là ma trận \(n\times m\), mỗi ô là một chỗ ngồi. Giá trị 2 là học sinh ngoan đã ngồi sẵn; 1 là ghế bị cấm; 0 là ghế trống cho học sinh nghịch ngợm. Giáo viên được chọn các ghế trống sẽ có học sinh nghịch ngợm ngồi. Học sinh ngoan không quay cóp, nhưng một học sinh nghịch ngợm sẽ quay cóp nếu có ít nhất một học sinh, ngoan hoặc nghịch ngợm, ở một trong bốn ô kề cạnh trên, dưới, trái, phải. Hãy tìm tổng số học sinh lớn nhất có thể ngồi trong lớp sao cho không có ai quay cóp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,m\) (\(1\le n,m\le80\)). Mỗi trong \(n\) dòng tiếp theo chứa \(m\) ký tự 0, 1 hoặc 2, mô tả lớp học.

Dữ liệu ra

In tổng số học sinh lớn nhất thỏa điều kiệ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. \(8\) điểm: \(n,m\le4\).
2. \(15\) điểm: mọi ô của ma trận đều là 0.
3. \(16\) điểm: \(n=2\).
4. \(52\) điểm: \(n\le15\).
5. \(19\) điểm: không có ràng buộc thêm.

Ví dụ

4 4
0100
0202
1000
2120

6

4 4
0000
0000
0000
0000

8

Nguồn

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

Đề 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.