Value of Array B

Interview

Time limit2sMemory limit512 MB

Summary

Swap at most one pair of rows or columns in an N by M grid to maximize the sum of all 2 by 2 block sums.

Level: Medium5 of 10
Topics: Array, Greedy, Prefix sum, Implementation
Solved: No attempts yet

Problem

Given an array A of size N×M, we can build an array B of size (N-1)×(M-1) as follows.

B[i][j] = A[i][j] + A[i+1][j] + A[i+1][j+1] + A[i][j+1] (1 ≤ i < N, 1 ≤ j < M)

The value of an array is the sum of all its elements.

In array A, we may swap the positions of any two rows or any two columns. Find the maximum possible value of array B after performing at most one swap in array A.

Input

The first line gives the size of array A, N and M. The next N lines give the elements of the array. The array consists of integers only.

Output

Print the maximum value among all arrays B that can be built.

Constraints

2 ≤ N, M ≤ 1,000
-1,000 ≤ Ai,j ≤ 1,000

Examples3

Example 1
Input
```
3 3
9 8 7
3 2 1
6 5 4
```
Expected output
```
92
```
Example 2
Input
```
3 4
1 2 1 1
2 1 1 2
2 1 1 1
```
Expected output
```
34
```
Example 3
Input
```
3 3
1 1 1
1 2 1
1 1 1
```
Expected output
```
20
```