Maximize Matrix Sum with Negation Operations

You are given an ( R \times C ) matrix ( a ) with ( |a_{i,j}| \le 10^4 ). You can perform a series of operations on the matrix to make the sum ( S = \sum_{i=1}^{R} \sum_{j=1}^{C} a_{i,j} ) as large as possible. The allowed operations are:

• rotR i k: Cyclically right-shift the elements of the \( i \)-th row by \( k \) positions. For example, for the row \( [1,2,3] \), rotR 1 1 changes it to \( [3,1,2] \).
• rotS j k: Cyclically down-shift the elements of the \( j \)-th column by \( k \) positions. For example, in the matrix \[ \begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ 10 & 11 & 12 \end{pmatrix} \] applying rotS 3 2 transforms the matrix to \[ \begin{pmatrix} 1 & 2 & 9\\ 4 & 5 & 12\\ 7 & 8 & 3\\ 10 & 11 & 6 \end{pmatrix} \].
• negR i: Multiply every element in the \( i \)-th row by \( -1 \). This operation is allowed only if none of the elements in that row has been flipped before.
• negS j: Multiply every element in the \( j \)-th column by \( -1 \). This operation is allowed only if none of the elements in that column has been flipped before.

Note that the rotation operations do not change the overall sum of the matrix, but they may alter the positions of elements. However, a proper sequence of negation operations can flip entire rows or columns (each at most once) and change the signs of the elements. In effect, after a sequence of valid negation operations, the element at position ( (i,j) ) becomes [ (-1)^{x_i+y_j} a_{i,j}, ] where ( x_i, y_j \in {0,1} ) indicate whether row ( i ) or column ( j ) has been flipped.

Your task is to compute the maximum possible value of ( S ) that can be achieved by applying a valid sequence of operations. Although rotation operations are available, note that they have no impact on the sum; only the negation operations matter. A simple strategy is to decide independently for each row whether to flip it (if its sum is negative) and then for each column, flip it if the sum of the column (after row flips) is negative.

Formally, given the matrix ( a ):

1. For each row ( i ), set a row flip factor ( r_i = -1 ) if ( \sum_{j=1}^{C} a_{i,j} < 0 ); otherwise, set ( r_i = 1 ).
2. For each column ( j ), compute ( s_j = \sum_{i=1}^{R} r_i \cdot a_{i,j} ) and set the column flip factor ( c_j = -1 ) if ( s_j < 0 ); otherwise, set ( c_j = 1 ).
3. Then, the resulting sum is ( \sum_{j=1}^{C} \left|\sum_{i=1}^{R} r_i \cdot a_{i,j}\right| ), which is maximized by the above choice.

Your program should read the input, perform these decisions, and output the maximum possible sum. ( \newline \newline \textbf{Note:} Although the problem statement mentions using as few operations as possible, you are only required to compute the maximum sum value achievable, not the actual sequence of operations.

inputFormat

The first line contains two integers ( R ) and ( C ) (the number of rows and columns). Each of the next ( R ) lines contains ( C ) integers representing the matrix ( a ).

outputFormat

Output a single integer, which is the maximum possible sum of the matrix after applying a valid sequence of negation operations.

sample

2 2
-1 2
3 -4

10