eolymp
bolt
Try our new interface for solving problems
Problems

Казак Ус и матрица

Казак Ус и матрица

Time limit 1 second
Memory limit 256 MiB

Казак Ус получил матрицу a размером n на m (т.е. матрица с n строк и m столбиков). Элементами этой матрицы являются только нули и единицы.

Казаку рассказали о манхэттенском расстоянии между элементами матрицы. Оказывается, что если один элемент матрицы находится в строке под номером i и столбце под номером j, а другой элемент находится в строке p и столбце k, то манхэттенским расстоянием между этими элементами считается число \mid i - p \mid + \mid j - k \mid (сумма модулей разностей координат элементов в матрице).

После этого Ус понял, что «красотой» любого элемента матрицы называют расстояние от этого элемента до ближайшего элемента, который является единицей. Заметьте, что «красота» любой единицы равна 0. К тому же Козак узнал, что в таких матрицах обязательно есть хотя бы одна единица.

Ваша задача несложная — найдите «красоту» наиболее «красивого» элемента матрицы.

Input data

Первая строка содержит два целых числа и m(1 \leq n,m \leq 20) — количество строк и столбцов в матрице.

Каждая из следующих n строк содержит m цифр a_{i,1}, a_{i,2},...,a_{i,m}(0 \leq a_{i,j} \leq 1) — значения элементов матрицы.

Гарантируется, что присутствует хотя бы одна единица.

Output data

Выведите одно число — максимальную «красоту».

Examples

Input example #1
2 3
010
000
Output example #1
2
Input example #2
3 4
0101
0001
0000
Output example #2
3

Note

Для матрицы из первого примера запишем «красоту» каждого ее элемента в матрицу:

1 0 1

2 1 2

Как мы видим, сразу два элемента матрицы — (вторая строка, первый столбец), и (вторая строка, третий столбик) имеют наибольшую «красоту» — 2.

Для второго примера матрица «красоты»:

1 0 1 0

2 1 1 0

3 2 2 1

Scoring

Решения, которые работают правильно для ограничений n = 1, наберут по крайней мере 30 баллов.

Решения, которые работают правильно для ограничений n = 2, наберут по крайней мере 30 баллов.

Author Mark Grishechkin