First note that using row/column rotations, we can place arbitrary elements on given rows or columns. For example, let sequence ~S = \{p_1, p_2, \dots, p_R\}~ of ~R~ elements we want to place in the first column. For ~i^\text{th}~ element we:

• If ~p_i~ is already in the first column, we place it out rotating the row by one.
• We rotate the column containing ~p_i~ so that it is in the ~i^\text{th}~ row.
• Rotate the row containing ~p_i~ so that it is placed into the first column.

Using this algorithm, we can place any chosen ~R~ elements in the first column and any chosen ~S~ elements in the first row. We can now negate all elements in the first row/column. If we repeat this procedure it follows that we can choose arbitrary ~a \cdot R + b \cdot S \le R \cdot S~ elements of the matrix and negate them.

The best solution is of course to negate all negative elements. Since this is not always possible, we need to choose such ~a~ and ~b~ that results in the smallest possible solution. Sorting the elements of the array and using dynamic programming easily yields the best ~a~ and ~b~.

Note that for each element, we use at most three rotations, and two negations this ensures that the number of operations is smaller than ~5 \cdot R \cdot S~.

Coding this in ~\mathcal O((\max\{R, S\})^4)~ solves the problem.