Столица Берляндии представляет собой прямоугольник размера n × m из одинаковых квадратных кварталов.

Беда! Пожар!

Известно, что загорелись k + 1 квартал (k + 1 ≤ n·m). Именно они — источники огня. При этом местоположения k загоревшихся кварталов (источников огня) известны, а местоположение одного загоревшегося квартала (источника огня) неизвестно. Все k + 1 местоположений — различны.

Огонь распространяется следующим образом: в нулевую минуту пожара горят только k + 1 источников огня. Каждую следующую минуту огонь перебрасывается на соседние кварталы от такого, который горит. Считайте, что кварталы горят очень долго (дольше времени, которое рассматривается в этой задаче). Соседними кварталами считаются те, которые касаются данного по стороне или углу.

Служба МЧС Берляндии хочет оценить минимальное возможное время, через которое пожар может распространиться на весь город. Помните, что местоположение k источников огня известно, а (k + 1)-й может располагаться в любом другом квартале.

Помогите МЧС найти минимальное время, через которое пожар может охватить весь город.