Largest Square of Crops

Alice owns a rectangular field divided into a grid of H rows and W columns. Some cells of the grid have crops planted (denoted by '1') while others are empty (denoted by '0'). She wants to know the side length of the largest square that can be formed using only cells containing crops.

For example, given the grid:

10111
10111
11111
10010
10010

The largest square that can be formed has a side length of 3.

Formally, if we denote the grid as a 2D array, you are to find the maximum integer s such that there exists a sub-grid of size s \times s for which every cell contains a crop. The recurrence relation used in the dynamic programming solution is given by:

\(dp[i][j] = \min(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1]) + 1\)

if the cell \((i,j)\) contains a crop, otherwise \(dp[i][j]=0\). The answer is the maximum value in the DP table.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two space-separated integers H and W representing the number of rows and columns of the grid.
2. The next H lines each contain a string of length W consisting of the characters '0' and '1', representing the grid rows.

outputFormat

Output a single integer to stdout — the side length of the largest square that can be formed using only cells containing a crop ('1').

## sample

5 5
10111
10111
11111
10010
10010

3

</p>