Problem Description

Cossack Beard got a matrix $a$ of size $n$ by $m$ (that is, a matrix with $n$ rows and $m$ columns). The elements of this matrix are only $0$ and $1$.

Someone introduced Cossack to the Manhattan distance between elements in a matrix. It turns out that if one element is in row $i$ and column $j$, and another element is in row $p$ and column $k$, then the Manhattan distance between these two elements is defined as $\mid i - p \mid + \mid j - k \mid$ (the sum of the absolute values of the coordinate differences).

After that, Beard understood that the "beauty" of any element in the matrix is the distance from that element to the nearest element with value $1$. Note that the "beauty" of any $1$ is $0$. Also, Cossack learned that in such a matrix, there is at least one $1$.

Your task is simple: find the "beauty" of the most "beautiful" element in the matrix.

Input Format

The first line contains two integers $n$ and $m$ $(1 \leq n,m \leq 20)$, the number of rows and columns of the matrix.

The next $n$ lines each contain $m$ digits $a_{i,1}, a_{i,2},...,a_{i,m}$ $(0 \leq a_{i,j} \leq 1)$, the values of the matrix elements.

It is guaranteed that there is at least one $1$.

Output Format

Output one number, the maximum "beauty".

2 3
010
000

2

3 4
0101
0001
0000

3

Hint

Sample Explanation

For the matrix in the first sample, write the "beauty" of each element in matrix form:

:::align{center} 1 0 1

2 1 2 :::

As we can see, there are two matrix elements, (row $2$, column $1$) and (row $2$, column $3$), that have the maximum "beauty", which is $2$.

For the second sample, its "beauty" matrix is:

:::align{center} 1 0 1 0

2 1 1 0

3 2 2 1 :::

Scoring Rules

A solution that works correctly under the constraint $n = 1$ will get at least $30$ points.

A solution that works correctly under the constraint $n = 2$ will get at least $30$ points.

The translation was completed by DeepSeek V3.

Translated by ChatGPT 5