Некоторая тюрьма может быть представлена в виде прямоугольной таблицы с $$$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 )$$$. Обратите внимание, что в любой клетке одновременно могут находиться сколько угодно заключенных.