Сережа играет в "Морской бой". Поле для игры представляет собой квадрат 10 x 10 клеток. На поле отмечены клетки, в которые Сережа уже стрелял. Однако, пока он не попал ни в один корабль противника. Требуется определить максимальную длину корабля, который может поместиться в небитых клетках этого поля. Корабль представляет из себя прямоугольник ширины 1 и располагается горизонтально или вертикально. (Гарантируется, что на поле есть хотя бы одна небитая клетка.)

В одной секретной лаборатории вывели новый вид маленьких монстров, размером чуть больше суслика. В ходе исследований ученые решили поставить следующий эксперимент. В центре комнаты устанавливается прямоугольный стол, поверхность которого разбита на \(N\) х \(M\) клеток размера 1 х 1. В начальный момент времени на некоторых его клетках располагаются монстры, смотрящие параллельно сторонам стола. По команде экспериментатора монстры начинают двигаться по прямой в ту сторону, в которую они смотрят, доходят до края стола и спрыгивают на пол. Там их собирает лаборант Петя и относит в клетку.

В некотором царстве, в некотором государстве было \(N\) городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |\(x_1\) - \(x_2\)| + |\(y_1\) - \(y_2\)|.

Император решил построить \(N\)+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.

Нелегкая задача выбрать место для столицы поручена Вам.

Государство Флатландия представляет собой прямоугольник размером \(M\) × \(N\), состоящий из единичных квадратиков. Флатландия разделена на K провинций (2 <= \(K\) <= 100). Каждая провинция представляет собой связное множество квадратиков, т.е. из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).

Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, которой принадлежит символ \(A\) (заглавная латинская буква \(A\)). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.

Король соседнего с Флатландией королевства Ректилания решил завоевать Флатландию. Для этого он хочет захватить столицу Флатландии. Однако он знает, что сил его армии недостаточно, чтобы сделать это сразу. Поэтому сначала он хочет окружить столичную провинцию, чтобы ослабить силы противника долгой блокадой, а потом захватить столицу.

Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой - второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.

Чтобы сберечь силы своей армии, король Ректилании хочет установить блокаду столичной провинции, захватив как можно меньше провинций. Помогите ему выяснить, сколько провинций требуется захватить. Захватывать столичную провинцию нельзя, поскольку для этого сил армии Ректилании пока недостаточно.