Whack-a-Mole is a game where there are several mole holes on the ground. Moles occasionally poke their heads out of the holes and then retreat back into them after a short time. The player's goal is to hit the moles on the head with a hammer when they poke their heads out; the more moles hit, the higher the score.

In the game, the hammer can only hit one mole at a time. If multiple moles poke their heads out simultaneously, the player can only hit all of them by swinging the hammer multiple times. You think this hammer is too useless, so you modified the hammer to increase its contact area with the ground, allowing it to hit a whole area at once. If we view the ground as an $m \times n$ matrix, where each element represents a mole hole, the hammer can cover all mole holes within an $R \times C$ area. However, the modified hammer has a drawback: each time the hammer is swung, it hits exactly one mole in every hole within the $R \times C$ area. This means that for every hole in the area covered by the hammer, there must be at least 1 mole, and if a hole contains more than 1 mole, only 1 mole will be hit in that hole. Therefore, each time the hammer is swung, exactly $R \times C$ moles are hit. Due to the delicate internal structure of the hammer, you cannot rotate it during the game (i.e., you cannot swap $R$ and $C$).

You can change the specifications of the hammer arbitrarily (i.e., you can choose the sizes of $R$ and $C$ at will), but the modification of the hammer can only be done before playing the game (i.e., you cannot change the hammer's specifications after hitting some of the moles). Your task is to find the minimum number of hammer swings required to hit all the moles.

Hint: Since you can set the hammer size to $1 \times 1$, this problem is always solvable.

Input

The first line contains two positive integers $m$ and $n$. The following $m$ lines each contain $n$ positive integers describing the map, where each number represents the number of moles in the corresponding hole.

Output

Output a single integer representing the minimum number of swings.

Examples

Input 1

3 3
1 2 1
2 4 2
1 2 1

Output 1

4

Note

Using a $2 \times 2$ hammer, swing once each at the top-left, bottom-left, top-right, and bottom-right positions.

Constraints

For 30% of the data, $m, n \le 5$; For 60% of the data, $m, n \le 30$; For 100% of the data, $1 \le m, n \le 100$, and other data are not less than 0 and not greater than $10^5$.