COVGAM - Thuốc diệt virus Covid-19
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte

Nói bộ não loài người càng bị đẩy đến cực hạn thì càng tiến hóa quả không sai. Mới đây, đứng trước tốc độ gia tăng chóng mặt số ca lây nhiễm cũng như tử vong của đại dịch Covid-19, một nhà khoa học thiên tài, tiến sĩ X, đã phát minh ra một phương pháp gọi là Tia gamma trùng sinh. Phương pháp này sử dụng tia gamma mang năng lượng cực lớn tác động lên 1 tế bào virus, vì năng lượng mà tế bào này hấp thụ quá lớn dẫn đến tính năng sinh lý của tế bào bị đảo ngược, biến virus trở thành một kháng thể, chiến đấu chống lại virus. Triết học võ thuật trung hoa gọi hiện tượng này là mượn lực đánh lực, lấy nhu thắng cương, người Việt ta còn gọi là gậy ông đập lưng ông.

Tuy vậy, phương pháp này không khả thi vì cơ thể người bình thường chỉ có thể chịu được tối đa 1 phát bắn tia gamma trùng sinh này, nếu quá liều sẽ gây hậu quả nghiêm trọng đến tính mạng. Tiến sĩ X tiếp tục nghiên cứu và phát hiện ra cơ thể người vốn đã có sẵn một số lượng kháng thể, và các kháng thể này chỉ tiêu diệt được virus nếu chúng được xếp cạnh nhau tạo thành 1 đội quân kháng thể, đội quân này càng lớn thì hiệu quả càng cao. Vì vậy, việc cần làm bây giờ là phải chọn bắn tia gamma vào tế bào virus nào để đạt được hiệu quả điều trị cao nhất.

Các tế bào người bệnh được trích xuất và mô tả dưới dạng một bảng m x n ô, mỗi ô đại diện cho 1 tế bào. Các ô được biểu diễn bởi số 1 nếu nó là tế bào kháng thể, số 0 nếu nó là tế bào virus. Các tế bào kháng thể (các ô số 1) nằm cạnh nhau (không tính đường chéo) sẽ tạo thành đội quân kháng thể. Một phát bắn gamma trùng sinh sẽ biến một tế bào virus bất kì thành tế bào kháng thể.

Yêu cầu: Cho sơ đồ tế bào, tính kích thước đội quân kháng thể lớn nhất có thể tạo được bằng cách bắn tối đa 1 tia gamma trùng sinh (có thể không bắn).

Input:

  • Dòng đầu tiên gồm 2 số m, n là kích thước của sơ đồ tế bào (m, n <= 1000)

  • M dòng tiếp theo mỗi dòng bao gồm N số nguyên mang giá trị 0 hoặc 1, tương ứng với các tế bào.

Output:

  • Một dòng duy nhất chứa kích thước của đội quân kháng thể lớn nhất.

Ví dụ

  • input
    5 5
    1 0 1 0 1
    1 1 1 0 1
    1 0 0 0 0
    1 1 1 0 0
    0 0 0 1 0
    output
    12

Giải thích: Bắn tia gamma vào tế bào ở vị trí hàng 2 cột 4

Back to Top