问题描述

在网格地图上有$n$个小人和$n$个房子。每个单位时间内，每个小人可以向相邻点水平或垂直移动一步。每移动一步需支付$1的费用，直到进入房子。每个房子只能容纳一个小人。

你的任务是计算将所有小人送入不同房子所需的最小总费用。输入地图中，'.'表示空地，'H'表示房子，'m'表示小人。网格足够大，可同时容纳多个小人，且允许小人经过房子所在点而不进入。

输入格式

• 输入包含多个测试用例。
• 每个用例首行为两个整数$N$和$M$，表示地图的行数和列数。
• 接下来的$N$行描述地图，保证'H'和'm'数量相等。
• 输入以$0\ 0$结束。

输出格式

• 对每个用例，输出最小总费用。

示例

输入样例 1

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

输出样例 1

2
10
28

数据来源

Pacific Northwest 2004