题目描述

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

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

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

在输入的地图场景中，$\red {“.”}$表示空地，$\red {“H”}$表示房子，$\red {“m”}$表示小人。

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

输入格式

输入包含多组测试数据。

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

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

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

当输入一行为$\red {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

提示

$\red {2≤N,M≤100}$