Problems
Binary Matrix 2
Binary Matrix 2
You are given a matrix of size \textbf{r}×\textbf{c}. Each of the elements can be either \textbf{0} or \textbf{1}. In each operation you can flip any element of this matrix, i.e. convert \textbf{0} to \textbf{1} or convert \textbf{1} to \textbf{0}. Your goal is to convert the matrix such that -
\begin{enumerate}
\item Each of the rows will have the same number of \textbf{1}s and
\item Each of the columns will have the same number of \textbf{1}s.
\end{enumerate}
What is the minimum number of operations required to achieve this?
\InputFile
Input starts with a positive integer \textbf{T} (~\textbf{1000}) which indicates the number of inputs.
Each case starts with two integers \textbf{m} and \textbf{n} (\textbf{1} ≤ \textbf{r}, \textbf{c} ≤ \textbf{40}), here \textbf{r} is the number of rows and \textbf{c} is the number of columns of the matrix. Each of the next \textbf{m} lines will have \textbf{n} integers each, either \textbf{0} or \textbf{1}.
\OutputFile
For each test case, output "\textbf{Case #: R}" in a single line, where \textbf{#} will be replaced by case number and \textbf{R} will be replaced by the minimum number of steps required to achieve the target matrix. Replace \textbf{R} by \textbf{-1} if it is not possible to reach target matrix.
Input example #1
3 2 3 111 111 3 3 011 011 011 2 3 001 000
Output example #1
Case 1: 0 Case 2: 3 Case 3: 1