CHUCK

Time limit1sMemory limit128 MB

Summary

Given a matrix with row/column rotation and one-time row/column sign flip operations, compute the maximum achievable total sum.

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

Problem

You are given a matrix with R rows and C columns. Every element has absolute value at most 10^4. You may apply the following operations any number of times.

Operation	Notation	Example
Rotate the i-th row of the matrix k elements to the right.	rotR i k	rotR 3 1 \(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} 1&2&3 \\ 4&5&6 \\ 9&7&8\\10&11&12 \end{pmatrix} \)
Rotate the j-th column of the matrix k elements down.	rotS j k	rotS 3 2 \(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} 1&2&9 \\ 4&5&12 \\ 7&8&3\\10&11&6 \end{pmatrix} \)
Multiply all elements in the i-th row by -1, if and only if none of them were multiplied before.	negR i	negR 2 \(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} 1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\)
Multiply all elements in the j-th column by -1, if and only if none of them were multiplied before.	negS j	negS 1 \(\begin{pmatrix} 1 & 2 & 3 \\ 0&0&0 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}\rightarrow \begin{pmatrix} -1 & 2 & 3 \\ 0 & 0 & 0\\ -7 & 8 & 9 \\ -10 & 11 & 12 \end{pmatrix}\)

Using these operations, make the sum of all elements of the matrix as large as possible.

Input

The first line contains two integers R and C (1 <= R, C <= 100), the number of rows and columns.

Each of the next R lines contains C integers. Every integer has absolute value less than 10^4.

Output

Print a single integer: the maximum possible sum of all elements of the matrix after applying the operations.

Examples2

Example 1

Input

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

Expected output

Example 2
Input
```
3 3
8 -2 7
1 0 -3
-4 -8 3
```
Expected output
```
34
```