Problem Description

Given an $N \times M$ grid matrix, each cell in the matrix is marked 0 or 1, indicating whether someone has stepped on this cell.

It is known that a person may start from any cell. After that, at each step they can only move one cell to the right or one cell down. After walking for several steps, the person can leave the matrix. All cells that this person passes through will be marked as 1, including the starting and ending cells. Note that the starting and ending cells do not have to be on the boundary of the matrix.

Please compute the minimum number of people who must have walked on the matrix.

Input Format

The first line contains two integers $N$ and $M$. The next $N$ lines each contain a binary string of length $M$, representing the grid matrix.

Output Format

Output one integer representing the answer.

5 5
00100
11111
00100
11111
00100

3

Hint

For all test cases, $1 \leq N, M \leq 20$, and the number of cells marked 1 does not exceed $200$.

Lanqiao Cup 2019 National Contest Group A Problem G (Group C Problem H).

Translated by ChatGPT 5