Coin Flips II

Sejun has N×M coins arranged in a rectangle with N rows and M columns. A coin showing heads is written as 0, and a coin showing tails is written as 1.

In one move, Sejun chooses a cell (a, b). Then every coin in a cell (i, j) satisfying 1 ≤ i ≤ a and 1 ≤ j ≤ b is flipped at the same time. Here, i is the row number counted from the top, and j is the column number counted from the left.

Find the minimum number of moves needed to make every coin show heads. Even if choosing (a, b) flips a×b coins, it counts as one move, not a×b moves.

The first line contains the height N and width M. N and M are positive integers no greater than 100.

The next N lines each contain M characters describing the coin states. Each character is either 0 or 1.

Print the minimum number of moves needed to make every coin show heads.