Cho bảng gồm \(n\) hàng và \(m\) cột. Mỗi ô của bảng được gán một số nguyên. Ta quy ước một hình L là tập hợp các ô vuông con của bảng như hình vẽ (hoặc là ảnh của hình vẽ qua phép quay \(\pm 90^{o}; \pm 180^{o})\)

Hình vẽ minh họa chữ L

Ví dụ:

• Một số chữ L hợp lệ:

• Một số chữ L không hợp lệ:

Yêu cầu của bài toán: Tìm tổng lớn nhất của các ô tạo thành chữ L

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên n và m, trong đó n và m là số hàng và số cột của bảng \((1 \leq n,m \leq 1000)\).

• n dòng tiếp theo, mỗi dòng gồm m số nguyên \(a_{ij}(1 \leq i \leq n,1 \leq j \leq m,\ - 10^{9} \leq a_{ij} \leq 10^{9})\), biểu thị giá trị trong các ô của bảng

Kết quả: ghi một số nguyên thỏa mãn yêu cầu của bài toán

Chú ý:

• 10% số điểm ứng với \(1 \leq n,m \leq 2\)

• 10 % số điểm ứng với \(n = 1\)

• 30% số điểm ứng với \(1 \leq n,m \leq 300\)

• 20% số điểm ứng với \(0 \leq a_{ij} \leq 10^{9}\) với \(1 \leq i \leq n,\ 1 \leq j \leq m\)

30% số điểm không có giới hạn gì thêm.