Crate Heist

On a bright spring day, you are reluctantly drawn back into a life of crime to help your old friend Patrick pull off one last heist. In a secured warehouse, expensive consumer widgets are stored in cubical crates stacked neatly in piles forming a three‐dimensional grid. The warehouse security relies on three cameras: a front camera that records the height of the tallest pile in each column, a side camera that captures the height of the tallest pile in each row, and a top camera that shows whether each pile is empty or not.

Patrick will measure the piles’ heights once he’s inside and send you the configuration. Your job is to remove (steal) as many crates as possible while rearranging the remaining crates into piles so that the three camera views stay exactly the same as before:

• The front view records, for every column j, the value \( c_j = \max_{i} B_{i,j} \).
• The side view records, for every row i, the value \( r_i = \max_{j} B_{i,j} \).
• The top view records whether or not each cell is empty. That is, for each cell \( (i,j) \), if the original configuration \( A_{i,j} > 0 \) then the remaining crates \( B_{i,j} \) must be at least 1, while if \( A_{i,j} = 0 \) then \( B_{i,j} = 0 \).

Here, \( B_{i,j} \) is the number of crates in cell \( (i,j) \) after the heist. You can only remove crates (i.e. decrease numbers) without reordering the piles arbitrarily except by reducing their height, and you cannot add new crates. Importantly, in order to fool the security system, the maximum height in every row and every column must remain intact.

Your task is to compute the maximum number of crates that can be stolen.

Explanation

Let \( A_{i,j} \) be the initial grid. Define the following:

• Total initial crates: \( T = \sum_{i,j} A_{i,j} \).
• For each row \( i \), \( r_i = \max_{j} A_{i,j} \).
• For each column \( j \), \( c_j = \max_{i} A_{i,j} \).
• For each cell \( (i,j) \) with \( A_{i,j} > 0 \) assign a baseline of 1 (to preserve non-emptiness).
• For each row \( i \), an additional \( r_i - 1 \) crates are needed in one cell where \( A_{i,j} = r_i \) and if possible it can be merged with a column peak.
• Similarly, for each column \( j \), an additional \( c_j - 1 \) crates are needed in one cell where \( A_{i,j} = c_j \).

If a cell is chosen to serve as the peak of both its row and column then the cell's value must equal \( r_i = c_j \) (in \( \LaTeX \) format), and the extra cost is only \( (r_i - 1) \) rather than \( (r_i-1)+(c_j-1) \). We can compute the maximum total saving by pairing rows and columns with the same peak value when possible. Let \( S \) be the saving, then the minimum required remaining crates is:

[ \text{minRemaining} = \text{baseline} + \left(\sum_{i}(r_i-1) + \sum_{j}(c_j-1) - S\right) ]

Thus, the answer is:

[ \text{answer} = T - \text{minRemaining} ]

It is guaranteed that the configuration given allows a valid rearrangement.

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of rows and columns, respectively).

Each of the next \( n \) lines contains \( m \) integers describing the grid \( A \). The integer \( A_{i,j} \) represents the number of crates at cell \( (i,j) \). It is guaranteed that \( 0 \le A_{i,j} \leq 10^9 \). For any cell with \( A_{i,j} > 0 \), the rearranged value \( B_{i,j} \) must be at least 1.

outputFormat

Output a single integer: the maximum number of crates that can be stolen while leaving a configuration that produces identical camera views.

sample

2 2
3 1
1 2

0