Description

2020-04-29 testdata updated.

Whac-A-Mole works like this: there are several mole holes on the ground, and moles will occasionally pop their heads out and then retract after a short time. The player's goal is to strike the mole's head with a hammer when it pops out; the more moles hit, the higher the score.

In the game, the hammer can hit only one mole per swing. If multiple moles pop out at the same time, the player must swing multiple times to hit them all. You think this hammer is too weak, so you modify it to increase the contact area with the ground so that it can hit a whole region at once. If we view the ground as an $m \times n$ grid where each cell is a mole hole, then the hammer can cover all holes in an $r \times c$ region. However, the modified hammer has a drawback: each time you swing it, within that region the hammer removes exactly one mole from each hole. In other words, every hole in the covered region must contain at least $1$ mole, and if a hole contains more than $1$ mole, only $1$ mole in that hole will be removed. Therefore, each swing removes exactly $r \times c$ moles. Because the hammer's internal structure is very delicate, you cannot rotate the hammer during the game (i.e., you cannot swap $r$ and $c$).

You may choose any hammer size (i.e., any $r$ and $c$), but you can only do this before playing (i.e., you cannot change the hammer size after removing some moles). Your task is to find the minimum number of swings needed to remove all moles.

Hint: Since you can set the hammer size to $1 \times 1$, this problem always has a solution.

Input Format

The first line contains two positive integers $m$ and $n$.

Each of the next $m$ lines contains $n$ non-negative integers describing the grid; each number is the number of moles in the corresponding hole.

Output Format

Print one integer, the minimum number of swings.

3 3
1 2 1
2 4 2
1 2 1

4

Hint

Sample Explanation:

Using a $2 \times 2$ hammer, swing once at each of the four positions: upper-left, lower-left, upper-right, and lower-right.

Constraints and Conventions:

• For $30\%$ of the testdata, $m, n \leq 5$.
• For $60\%$ of the testdata, $m, n \leq 30$.
• For $100\%$ of the testdata, $1 \leq m, n \leq 100$. All other numbers are between $0$ and $10^5$ inclusive.

Translated by ChatGPT 5