Hai hình chữ nhật

Cho ma trận A gồm M hàng và N cột. Các phần tử trong ma trận chỉ nhận giá trị 0 hoặc 1.

Trong ma trận này, hãy tìm hai hình chữ nhật con thỏa mãn:

• Mỗi hình chữ nhật chỉ chứa các giá trị 0
• Các cạnh của hình chữ nhật song song với các cạnh của ma trận
• Hai hình chữ nhật không giao nhau, nghĩa là không có ô nào thuộc cả hai hình chữ nhật cùng lúc
• Tổng diện tích của hai hình chữ nhật là lớn nhất

Hãy in ra tổng diện tích lớn nhất tìm được.

Lưu ý: Nếu không thể chọn được hai hình chữ nhật thỏa mãn các điều kiện trên, hãy in ra 0.

Đầu vào: Dòng đầu tiên chứa hai số nguyên M và N ($0 \lt M,N \leq 1000$).

Dòng thứ i trong M dòng tiếp theo chứa N số nguyên $A_{i,1}, A_{i,2}, ..., A_{i,N}$.

Dữ liệu đảm bảo rằng $A_{i,j} \in \{0,1\}$.

Đầu ra: Một số nguyên duy nhất là tổng diện tích lớn nhất của hai hình chữ nhật tìm được.

Giải thích: Hai hình chữ nhật tối ưu được tô màu đỏ như hình bên dưới:

Ví dụ 1:

Đầu vào:

6 7
0 1 0 0 0 0 0
0 0 0 0 1 0 0
1 0 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 0 0
0 0 1 0 0 1 0

Đầu ra:

20