Dấu cộng có tổng lớn nhất

Bối cảnh

Một hệ thống radar đánh giá "điểm giao" bằng hình dấu cộng gồm một ô trung tâm và bốn ô kề trực tiếp theo trên, dưới, trái, phải. Chỉ những ô không nằm trên biên ma trận mới có thể làm tâm, vì dấu cộng phải có đủ bốn nhánh.

Với mỗi tâm hợp lệ (i,j), tổng tín hiệu là tổng của đúng 5 ô nói trên. Nhiệm vụ là tìm dấu cộng có tổng lớn nhất; nếu có nhiều lựa chọn cùng tổng, chọn tâm có hàng nhỏ hơn rồi cột nhỏ hơn. Nếu ma trận không có tâm hợp lệ (rows<3 hoặc cols<3), in NO.

Bài Medium rèn khả năng biến một hình dạng không phải hàng/cột/đường chéo thành tập tọa độ cụ thể và xử lý biên an toàn.

Khác với bài tổng hàng/cột, chỉ cần đọc đúng 5 tọa độ tương đối quanh mỗi tâm.

Yêu cầu

1. Nếu rows<3 hoặc cols<3, không có dấu cộng.
2. Duyệt i từ 1 đến rows-2 và j từ 1 đến cols-2.
3. Tính tổng 5 ô và cập nhật max.

Input

Dòng 1: rows cols; sau đó ma trận.

Output

NO nếu không có tâm hợp lệ; ngược lại maxSum row col.

Ràng buộc

1 ≤ rows,cols ≤ 100, |a[i][j]| ≤ 10^9.

Ví dụ 1

Input

3 3
1 2 3
4 5 6
7 8 9

Output

25 1 1

Giải thích

Ma trận 3×3 chỉ có đúng một tâm dấu cộng hợp lệ là ô nội bộ (1,1). Năm ô của dấu cộng là tâm 5, trên 2, dưới 8, trái 4, phải 6; tổng bằng 5+2+8+4+6 = 25. Vì không có tâm khác để cạnh tranh, output là 25 1 1.

Ví dụ 2

Input

2 4
1 2 3 4
5 6 7 8

Output

NO

Giải thích

Ma trận có 2 hàng, nên không tồn tại ô nào vừa có hàng phía trên vừa có hàng phía dưới. Điều kiện tạo dấu cộng 5 ô vì thế không thỏa ở mọi vị trí, bất kể số cột là 4. Theo yêu cầu bài, khi không có tâm hợp lệ phải in NO.

Thông tin học tập

• Module: M03
• Buổi: B11
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: 2D static arrays, local neighborhood, cross shape, optimization, coordinates
• Giới hạn kiến thức: B01-B11
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100