cho.shCHUCK
Time limit1sMemory limit128 MBDescription
Examples2
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.
Loading...