Maximize the matrix sum

Time limit2sMemory limit256 MB

Summary

Reorder entries by rotating rows and columns and flipping row and column signs to maximize the sum of all cells.

Level: Hard8 of 10
Topics: Math, Greedy, Sorting, Matrix
Solved: No attempts yet

Problem

You are given a matrix with $R$ rows and $C$ columns. Every cell holds one integer, and you may apply the four operations below in any order, as many times as you like.

Notation	Meaning
`rotR i k`	Rotate row $i$ to the right by $k$ cells. ( $1 \le i \le R$ , $1 \le k < C$ )
`rotC j k`	Rotate column $j$ downward by $k$ cells. ( $1 \le j \le C$ , $1 \le k < R$ )
`negR i`	Multiply every element of row $i$ by $-1$ . ( $1 \le i \le R$ )
`negC j`	Multiply every element of column $j$ by $-1$ . ( $1 \le j \le C$ )

Applying each operation once to the matrix $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$ gives the following results.

rotR 3 1 gives $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 7 & 8 \end{pmatrix}$ .
rotC 1 2 gives $\begin{pmatrix} 4 & 2 & 3 \\ 7 & 5 & 6 \\ 1 & 8 & 9 \end{pmatrix}$ .
negR 2 gives $\begin{pmatrix} 1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \end{pmatrix}$ .
negC 2 gives $\begin{pmatrix} 1 & -2 & 3 \\ 4 & -5 & 6 \\ 7 & -8 & 9 \end{pmatrix}$ .

Find the largest sum of all elements of the matrix that you can reach.

Input

The first line contains two natural numbers R and C ( $1 \le R, C \le 100$ ), separated by a space.

Each of the next R lines contains C integers separated by spaces. The absolute value of each integer is at most $10^4$ .

Output

Print the largest reachable sum of all elements on the first line. Do not print the list of operations you used.

Examples3

Example 1

Input

3 4
1 -2 5 200
-8 0 -4 -10
11 4 0 100

Expected output

Example 2
Input
```
1 1
-5
```
Expected output
```
5
```
Example 3
Input
```
2 2
1 2
3 -4
```
Expected output
```
8
```