주차장

주차장은 R행 C열의 직사각형 격자이다. 격자에는 자동차 N대와 주차 구역 M개가 있다. 모든 자동차는 주차 구역에 배정되어 주차해야 한다. 이동 제한 때문에 자동차는 격자의 상하좌우 방향으로만 움직일 수 있고, 1초에 한 칸씩 이동한다.

각 자동차를 현재 위치에서 가장 가까운 주차 구역으로 보내는 선택이 항상 최적은 아니다. 예를 들어 다음과 같은 주차장이 있다.

.C.....P.X...XX.......X..PXX.....C.....

C는 자동차, P는 주차 구역, X는 벽, .은 빈 칸이다.

아래쪽 자동차가 가장 가까운 주차 구역에 주차하면, 왼쪽 위 자동차는 가장 오른쪽에 있는 주차 구역에 가야 하므로 그 자동차가 주차하기까지 14초가 걸린다. 하지만 아래쪽 자동차가 오른쪽 주차 구역으로 가면, 두 자동차 모두 6초 안에 주차를 마칠 수 있다.

현재 주차장의 모양, 자동차의 위치, 주차 구역의 위치가 주어진다. 모든 자동차가 서로 다른 주차 구역에 주차를 마칠 때까지 걸리는 시간의 최솟값을 구하라. 자동차는 매우 작기 때문에 이동 중에 여러 자동차가 같은 칸에 동시에 있을 수 있다. 자동차는 빈 칸과 주차 구역을 지나갈 수 있지만, 벽은 지나갈 수 없다.

모든 자동차를 주차시킬 수 없다면 -1을 출력한다.

첫째 줄에 주차장의 세로 크기 R과 가로 크기 C가 주어진다. R과 C는 모두 50 이하이다.

둘째 줄부터 R개의 줄에는 주차장의 정보가 주어진다. 각 줄은 위에서 설명한 문자들로만 이루어져 있다. 자동차의 개수와 주차 구역의 개수는 각각 0 이상 100 이하이다.

첫째 줄에 모든 자동차가 주차를 마칠 때까지 걸리는 시간의 최솟값을 출력한다. 자동차가 한 대도 없으면 0을 출력한다. 모든 자동차를 주차시킬 수 없다면 -1을 출력한다.