Minimum Flips to Ensure Ones in Each Row and Column

Given a binary matrix of size \( m \times n \) consisting of 0s and 1s, your task is to determine the minimum number of flips (converting a 0 to a 1) required such that every row and every column contains at least one 1.

In one flip, you can choose any cell with value 0 and change it to 1. The key observation is that by strategically flipping at intersections of rows and columns that have no 1, one flip can serve both a row and a column. Formally, if \( r \) is the number of rows without any 1 and \( c \) is the number of columns without any 1, the answer is \( \max(r, c) \).

This problem tests your ability to analyze matrix properties and optimize operations under given constraints.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers \( m \) and \( n \) — the number of rows and columns respectively.
• The next \( m \) lines each contain \( n \) integers (each either 0 or 1) separated by spaces representing the matrix.

outputFormat

Output to stdout a single integer — the minimum number of flips required to ensure that every row and every column contains at least one 1.## sample

3 3
0 0 0
0 0 0
0 0 0

3