На стоянці знаходиться кілька автомобілів і паркувальних місць. Усім автомобілям необхідно роз'їхатися по парковках. Згідно правил дорожнього руху кожному автомобілю дозволено пересуватися тільки паралельно кордонам стоянки та зі швидкістю одна клітина в одиницю часу.

Зазвичай машини їдуть на найближче паркувальне місце. Але для деяких машин це не найкраще рішення. Розглянемо наступну стоянку ('C' позначає машину, 'P' паркувальне місце, 'X' стіну, а '.' позначає вільне місце):

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

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

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

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

Знайти найменший час, за який всі машини зможуть зайняти місце для паркування (за умови, що автомобілі діють як описано вище). Всі машини починають рух з вільного місця. Автомобілі досить малі, тому в кожній клітині одночасно може перебувати будь-яка кількість автомобілів. Машини можуть їздити по вільним місцям і паркувальним майданчикам, але не через стіни. По завершенню пересування машин кожне паркувальне місце має бути зайнято не більш ніж одним автомобілем.

Вхідні дані

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

Вихідні дані

Для кожного тесту вивести в окремому рядку найменший час, за який всі машини роз'їдуться по паркувальним майданчикам. Якщо роз'їхатися по парковках усім машинам неможливо, то вивести -1. Якщо машини на парковці відсутні, то вивести 0.