Whack-A-Mole Minimum Swings

This problem is a twist on the classic whack‐a‐mole game. Consider an m × n grid where each cell represents a mole hole. Initially, each cell contains a given number of moles. Before the game starts, you can modify your hammer. The hammer, when swung, covers an r × c contiguous submatrix (with r and c chosen arbitrarily with 1 ≤ r ≤ m and 1 ≤ c ≤ n, and you cannot rotate the hammer, i.e. you cannot swap r and c). When you swing the hammer, every cell in the covered r × c region must contain at least one mole. The swing will reduce the number of moles in every cell in that region by exactly 1 (even if some cell contains more than 1 mole, only 1 mole is removed from that cell).

Your task is to choose a hammer configuration (i.e. choose values of r and c before any swings) and a sequence of swings in order to remove all the moles in the grid. It is guaranteed that using a 1 × 1 hammer always provides a solution. Compute the minimum number of swings needed to eliminate all the moles.

For clarity, if you denote the grid by A with dimensions m × n, a hammer swing subtracts 1 from every cell in some submatrix of size r × c. If we represent the hammer swing as a matrix of ones, then a valid sequence of swings is a decomposition of A into a sum of these r × c blocks where the total number of swings is minimized.

All formulas are rendered in LaTeX format. For example, the grid size is given as \(m\times n\) and the hammer size as \(r\times c\).

inputFormat

The first line contains two integers m and n (1 ≤ m, n ≤ 50), denoting the number of rows and columns of the grid.

Each of the next m lines contains n integers. The \(j\)-th integer in the \(i\)-th line is \(A_{i,j}\) (0 ≤ \(A_{i,j}\) ≤ 10⁹), which represents the number of moles initially in cell \((i,j)\).

You may assume that there is always a valid way to remove all moles.

outputFormat

Output a single integer representing the minimum number of hammer swings required to remove all the moles from the grid.

sample

1 1
5

5