Vấn đề này được thiết kế theo các bài trong kì thi OLP tin học sinh viên, giới hạn (subtask) được xếp ở cuối.

Trong toán học, phép toán hai ngôi nhận vào hai biến số và cho ra một kết quả - các biến và kết quả đều thuộc một tập hợp, từ đó xây dựng nên các nhóm trừu tượng. Trong lập trình, phép toán hai ngôi được sử dụng để thực hiện các phép tính số học, logic, ... đồng thời tổng quát hóa các phương pháp sử dụng hai biến số.

Để hiểu rõ hơn về các tính chất của khái niệm này, thầy giáo Hans cho cả lớp bài tập về nhà sử dụng một phép toán hai ngôi mới, gọi là phép chấm. Phép chấm được định nghĩa như sau:

\[~x \bullet y = sgn(xy)*(|x| + |y|)~\]

Với \(sgn(x)\) là dấu của \(x\): \(sgn(x) = -1\) nếu \(x < 0\), \(sgn(x) = 1\) nếu \(x > 0\), quy ước \(sgn(0) = 0\).

Từ đó, thầy Hans định nghĩa phép lấy chấm các phần tử trên dãy số nguyên \((u)\): \({\Large{\Xi}}_{i = a}^{b}u_i = u_a \bullet u_{a + 1} \bullet \ldots \bullet u_b\).

Bài tập về nhà mà thầy Hans giao liên quan tới làm việc trên ma trận \((v_{ij})_{m*n}\) sử dụng phép chấm. Các hàng của ma trận được đánh số từ \(1\) tới \(m\) từ trên xuống dưới, các cột của ma trận được đánh số từ \(1\) tới \(n\) từ trái qua phải. Giá trị của số nằm ở hàng \(i\), cột \(j\) \((1 \le i \le m; 1 \le j \le n)\) được ký hiệu là \(v_{i, j}\).

Yêu cầu

Xác định giá trị lớn nhất của chấm các phần tử rìa trong ma trận con từ ma trận \((v_{ij})_{m*n}\).

Cụ thể hơn, bạn cần cần tìm giá trị lớn nhất của biểu thức \({\Large{\Xi}}_{i = b}^{b' - 1}v_{a,i} \bullet {\Large{\Xi}}_{i = a}^{a' - 1}v_{i,b'} \bullet {\Large{\Xi}}_{i = b + 1}^{b'}v_{a',i} \bullet {\Large{\Xi}}_{i = a + 1}^{a'}v_{i,b}\) với mọi bộ số \((a, b, a', b')\) thỏa mãn \(1 \le a < a' \le m\) và \(1 \le b < b' \le n\).

Dữ liệu

Vào từ thiết bị nhập chuẩn có định dạng:

• Dòng đầu chứa số hai số nguyên dương \(m\), \(n\);
• Tiếp theo là \(m\) dòng, dòng thứ \(i\) \((1 \le i \le m)\) gồm \(n\) số nguyên không âm \(v_{i,1}, v_{i,2}, ..., v_{i,n}\), các số có giá trị tuyệt đối không vượt quá \(10^9\).

Kết quả

Đưa ra thiết bị xuất chuẩn một số nguyên duy nhất là kết quả bài toán.

Ví dụ

Dữ liệu vào:

3 6
1 -6 7 8 9 10
-1 1 2 3 4 5
1 -9 8 7 6 5

Kết quả ra:

81

Giải thích:

Ma trận con \(\begin{bmatrix} -6 & 7 & 8 & 9 & 10\\ 1 & 2 & 3 & 4 & 5\\ -9 & 8 & 7 & 6 & 5\\ \end{bmatrix}\) có chấm các phần tử rìa là lớn nhất bằng \((-6 \bullet 7 \bullet 8 \bullet 9) \bullet (10 \bullet 5) \bullet (8 \bullet 7 \bullet 6 \bullet 5) \bullet (1 \bullet -9) = 81\) .

Giới hạn

Subtask \(1\) (\(20\%\) số điểm): \(m, n \le 10\).

Subtask \(2\) (\(20\%\) số điểm): \(m, n \le 100\).

Subtask \(3\) (\(20\%\) số điểm): \(m*n \le 10^5\), các phần tử của ma trận đều không âm.

Subtask \(4\) (\(40\%\) số điểm): \(m*n \le 10^5\).