Mission Improbable

Interview

Time limit1sMemory limit512 MB

Summary

Given a grid of pile heights, find the maximum number of crates that can be removed while keeping every row maximum, column maximum, and empty/non-empty pattern unchanged.

Level: Medium6 of 10
Topics: Greedy, Array, Implementation, Math
Solved: No attempts yet

Problem

It is a sunny day in spring and you are about to meet Patrick, a close friend and a former partner in crime. Patrick lost most of his money betting on programming contests, so he has to pull off another job, and for that he needs your help. You retired from a life of crime and you are reluctant at first, but there is no harm in listening to his plan.

A shipment of expensive widgets is stored in a nearby warehouse and Patrick intends to steal as much of it as he can. Getting into the building, dealing with the guards and passing through the laser beams are the usual heist work. The heart of the warehouse is protected by a security system that Patrick cannot disable, and that is where he needs you.

The shipment is stored in large cubical crates, all of the same size. The crates are stacked in neat piles that form a grid with $r$ rows and $c$ columns. Once per hour the security system takes three pictures. The front camera records the height of the tallest pile in each column, the side camera records the height of the tallest pile in each row, and the top camera records whether each position is empty or not. If any of the three images changes, the alarm goes off.

The picture below shows one grid of heights and the view from each camera.

Figure C.1: A grid of heights and the matching camera views

Once Patrick is inside, he measures the height of every pile and sends the numbers to you. He can then restack the remaining crates on the same grid in any way he likes. For the next three pictures to look exactly like the current ones, all of these conditions must hold.

In every column, the tallest pile keeps the same height.
In every row, the tallest pile keeps the same height.
A position that held at least one crate still holds at least one crate, and a position that was empty stays empty.

In the grid of Figure C.1 it is possible to steal nine crates. The picture below shows one arrangement after the heist that looks identical to the security system.

Figure C.2: One possible grid of heights after the heist

Compute the largest number of crates Patrick can carry away while satisfying all three conditions.

Input

The first line contains two integers $r$ and $c$ ( $1 \le r \le 100$ , $1 \le c \le 100$ ), the number of rows and the number of columns of the grid.

Each of the next $r$ lines contains $c$ integers, the heights in crates of the piles in that row. Every height is between $0$ and $10^9$ inclusive.

Output

Print the maximum number of crates that can be stolen without setting off the alarm.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
2 3
50 20 3
20 10 3
```
Expected output
```
30
```
Example 3
Input
```
1 1
0
```
Expected output
```
0
```