집으로 가는 길

격자 지도에는 같은 수의 어린이와 집이 있다. 한 단위 시간마다 각 어린이는 위, 아래, 왼쪽, 오른쪽으로 인접한 칸 하나만 이동할 수 있으며, 어린이가 집에 도착할 때까지 이동 한 번마다 1달러가 든다.

각 집에는 어린이 한 명만 들어갈 수 있다. 모든 어린이를 서로 다른 집으로 보내는 데 필요한 총 비용의 최솟값을 구하라.

지도에서 .은 빈 칸, H는 집, m은 어린이를 뜻한다. 이동 중에는 여러 어린이가 같은 칸에 동시에 있을 수 있고, 어떤 어린이가 최종 목적지가 아닌 집 칸을 지나가는 것도 가능하다.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 지도의 행 수 N과 열 수 M이 주어진다. 이어지는 N개의 줄에는 지도가 주어진다.

N과 M은 2 이상 100 이하이다. 지도에 있는 H와 m의 개수는 같으며, 집은 최대 100개이다.

N M이 0 0이면 입력이 끝난다.

각 테스트 케이스마다 모든 어린이를 서로 다른 집으로 보내는 데 필요한 최소 비용을 한 줄에 하나씩 출력한다.