Некоторая тюрьма может быть представлена в виде прямоугольной таблицы с \(n\) строками и \(m\) столбцами, каждая клетка которой — камера. Таким образом, всего есть \(n \cdot m\) камер. В тюрьме \(n \cdot m\) заключенных, по одному в каждой камере. Обозначим клетку-камеру в \(i\)-й строке и в \(j\)-м столбце как \((i, j)\).
В клетке \((r, c)\) заключенные прорыли тоннель, который можно использовать для побега! Чтобы не попасться, они будут убегать ночью.
В начале ночи каждый заключенный находится в своей клетке. Когда наступает ночь, они могут начать двигаться в соседние клетки. Формально, за одну секунду заключенный, находящийся в клетке \((i, j)\), может переместиться в любую из клеток \(( i - 1 , j )\) , \(( i + 1 , j )\) , \(( i , j - 1 )\) или \(( i , j + 1 )\), если они находятся на территории тюрьмы. Он также может остаться в клетке \((i, j)\).
Заключенные хотят знать минимальное необходимое время для того, чтобы все они смогли собраться в клетке \(( r , c )\). Обратите внимание, что в любой клетке одновременно могут находиться сколько угодно заключенных.