The Way Home

A grid map contains the same number of children and homes. During each unit of time, every child may move one cell up, down, left, or right. You must pay 1 dollar for each move made by a child until that child reaches a home.

Each home can receive exactly one child. Find the minimum total cost needed to send all children to distinct homes.

In the map, . is an empty cell, H is a home, and m is a child. During movement, multiple children may occupy the same cell at the same time, and a child may pass through a home cell that is not their final assigned home.

The input contains one or more test cases. The first line of each test case contains two integers N and M, the number of rows and columns of the map. The next N lines describe the map.

Both N and M are between 2 and 100, inclusive. The number of H cells equals the number of m cells, and there are at most 100 homes.

The input ends with a line containing 0 0.

For each test case, output one line containing the minimum cost needed to send every child to a distinct home.