题目描述

在网格地图上有 $n$ 个小人和 $n$ 个房子，在单位时间内，每个小人都可以水平或垂直移动一个格子。

每个小人移动一步都会花费 $1$ 美金，直到他进入到一间房子里为止，每间房子只能容纳一人。

你需要计算，所有小人都进入到房子里，你所需要花费的金额最少是多少。

在输入的地图场景中：

• . 表示空地
• H 表示房子
• m 表示小人

地图足够大，并且小人在不进入房间的情况下，也可以踩在有房间的格子上。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个整数 $N$ 和 $M$，表示地图大小为 $N$ 行 $M$ 列。

接下来 $N$ 行，每行包含 $M$ 个字符，表示完整的地图场景。

房屋数量与人数量相同，且不超过 $100$ 个。

当输入一行为 0 0 时，表示输入终止。

输出格式

每组数据输出一个整数，表示最少花费（即所有小人的最短移动距离之和）。

每个结果占一行。

样例

输入样例：

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

输出样例：

2
10
28

样例解释

第一组：

• 地图：

.m
H.

小人(1,2)到房子(2,1)的曼哈顿距离 = |1-2| + |2-1| = 2，花费2。

第二组：

• 地图：

HH..m
.....
.....
.....
mm..H

人和房子各有3个。最优匹配使得总距离最小=10。

第三组：

• 地图中有4个小人和4个房子（H在中间列，小人在第四行）。 通过计算匹配得到总距离=28。

数据范围

• $2 \leq N, M \leq 100$
• 房屋数量 = 小人数 ≤ 100
• 多组测试，以 0 0 结束

时空限制

• 时间限制：1 秒
• 空间限制：64 MB