Minimum Monotonic Paths Covering Ones

You are given an N × M grid. Each cell is marked with either 0 or 1, indicating whether someone has stepped on that cell. A person’s walk is defined as follows:

• The person may start at any cell in the grid.
• From the current cell, the person can only move one step to the right or one step downward.
• The person takes a sequence of such steps (possibly zero steps) and eventually exits the grid. Note that the starting cell and the cell from which the person exits (the last cell inside the grid) do not necessarily lie on the grid border.
• Every cell visited by the person (including the starting cell and the last cell inside the grid) is marked with a 1.

The final grid is produced as the union of the cells visited by one or more people. Your task is to determine the minimum number of people that must have walked on the grid in order to explain the pattern of 1s.

Additional Information (in LaTeX):

The allowed moves form a monotonic (right/down) lattice path. That is, if a person starts at cell $(i,j)$ then subsequent cells in his/her path satisfy $$ (i_1,j_1),\,(i_2,j_2),\,\ldots,\,(i_k,j_k) $$ with $$ i\le i_1\le i_2 \le \cdots \le i_k \quad\text{and}\quad j\le j_1\le j_2 \le \cdots \le j_k, $$ with the additional condition that for each adjacent pair, we have either $$ i_{t+1}=i_t \text{ and } j_{t+1}=j_t+1 $$ or $$ j_{t+1}=j_t \text{ and } i_{t+1}=i_t+1. $$

Hint: It can be shown that if the grid pattern is valid (i.e. it is possible to obtain the given grid by a collection of such walks), then the minimum number of people needed is equal to the \#(1's) minus the maximum matching in a bipartite graph constructed as follows:

• Consider every cell with a 1 as a vertex. Assign an index id = i*M + j for cell at row i and column j.
• Partition the vertices into two sets: those where (i+j) is even (left set) and odd (right set).
• For every cell in the left set, if its right neighbor (i, j+1) or bottom neighbor (i+1, j) exists and is also 1, add an edge from the left cell to that neighbor.

Then the answer is given by:

$$\text{answer} = \text{total number of }1\text{'s} - \text{(size of maximum matching)}. $$

inputFormat

The first line contains two integers N and M (the number of rows and columns respectively).

Each of the next N lines contains M integers (each either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer which is the minimum number of people that must have walked on the grid.

sample

2 2
1 1
1 1

2