На стоянке находится несколько автомобилей и парковочных мест. Всем автомобилям необходимо разъехаться по парковкам. Из-за правил дорожного движения каждому автомобилю разрешено двигаться только параллельно границам стоянки и со скоростью одна клетка в единицу времени.

Обычно машины едут на ближайшее парковочное место. Но для некоторых машин это не лучшее решение. Рассмотрим следующую стоянку ('C' обозначает машину, 'P' парковочное место, 'X' стену, а '.' обозначает свободное место):

.C.....P.X...

XX.......X..P

XX.....C.....

Если машина, находящаяся внизу, будет двигаться к ближайшей парковке, то машина слева вверху доедет до другого парковочного места за 13 единиц времени. Однако если нижняя машина направится к правой парковке, то обе машины смогут разъехаться по парковочным местам за 6 единиц времени.

Найти наименьшее время, за которое все машины смогут занять место для парковки (при условии, что автомобили действуют как описано выше). Все машины начинают движение со свободного места. Автомобили достаточно малы, поэтому в каждой клетке одновременно может находиться любое количество автомобилей. Машины могут ездить по свободным местам и парковкам, но не через стены. По завершению передвижения машин каждое парковочное место должно быть занято не больше чем одним автомобилем.

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

Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа row и column (1 ≤ row, column ≤ 50) - размеры парковки. Следующие row строк задают парковку в формате, описанном выше. Количество машин и парковочных мест для каждого теста не более 100.

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

Для каждого теста вывести в отдельной строке наименьшее время, за которое все машины разъедутся по парковочным местам. Если разъехаться по парковкам всем машинам невозможно, то вывести -1. Если машины на парковке отсутствуют, то вывести 0.