Казак Ус получил матрицу a размером n на m (т.е. матрица с n строк и m столбиков). Элементами этой матрицы являются только нули и единицы.
Казаку рассказали о манхэттенском расстоянии между элементами матрицы. Оказывается, что если один элемент матрицы находится в строке под номером i и столбце под номером j, а другой элемент находится в строке p и столбце k, то манхэттенским расстоянием между этими элементами считается число ∣i−p∣+∣j−k∣ (сумма модулей разностей координат элементов в матрице).
После этого Ус понял, что «красотой» любого элемента матрицы называют расстояние от этого элемента до ближайшего элемента, который является единицей. Заметьте, что «красота» любой единицы равна 0. К тому же Козак узнал, что в таких матрицах обязательно есть хотя бы одна единица.
Ваша задача несложная — найдите «красоту» наиболее «красивого» элемента матрицы.
Первая строка содержит два целых числа и m (1≤n,m≤20) — количество строк и столбцов в матрице.
Каждая из следующих n строк содержит m цифр ai,1,ai,2,...,ai,m (0≤ai,j≤1) — значения элементов матрицы.
Гарантируется, что присутствует хотя бы одна единица.
Выведите одно число — максимальную «красоту».
Для матрицы из первого примера запишем «красоту» каждого ее элемента в матрицу:
1 0 1
2 1 2
Как мы видим, сразу два элемента матрицы — (вторая строка, первый столбец), и (вторая строка, третий столбик) имеют наибольшую «красоту» — 2.
Для второго примера матрица «красоты»:
1 0 1 0
2 1 1 0
3 2 2 1
Решения, которые работают правильно для ограничений n=1, наберут по крайней мере 30 баллов.
Решения, которые работают правильно для ограничений n=2, наберут по крайней мере 30 баллов.