Дистанционный практикум по программированию

Уровень некоторой компьютерной игры представляет собой плоский лабиринт. Вам дана карта этого лабиринта, которая выглядит как прямоугольное клетчатое поле размером M×N клеток. Некоторые из клеток пусты, в других находятся непроходимые стены.

В начальный момент времени в различные пустые клетки лабиринта были телепортированы несколько игроков. За одну секунду каждый игрок может перейти в одну из соседних четырёх клеток (если там нет стены) либо остаться стоять на месте. Игроки не могут выходить за пределы лабиринта.

Чтобы выполнить миссию игры, необходимо собрать в одной любой клетке не менее чем K любых игроков. Определите, за какое минимальное время это можно сделать.

Входные данные

В первой строке входных данных записаны три целых числа M, N, K.

В следующих M строках записано по N символов '.', '#' или '*', описывающих карту лабиринта. Символом '.' обозначена свободная клетка, символом '#' − клетка со стеной, символом '*' − клетка с одним из игроков.

Ограничения:

·        2 ≤ M, N ≤ 200, 2 ≤ K ≤ 100;

·        Всего в лабиринте находится не более 100 игроков.

Выходные данные

Одно целое число − минимальное количество секунд, за которое не менее чем K игроков смогут собраться в одной клетке.

Если решения нет, выведите -1.

Пример ввода 1 4 5 3 ..... *.#.* ###.. *...* Пример вывода 1 3

Пример ввода 2 3 3 2 ..* ### .*. Пример вывода 2 -1

Система оценивания.

Подзадача 1 (до 50 баллов): 1 ≤ M, N ≤ 50.

Подзадача 2 (до 50 баллов): 50 < M, N ≤ 200.

В обеих подзадачах баллы за каждый тест начисляются независимо. По запросу сообщается результат проверки на каждом тесте.