小熊 Mecho 发现了一点宝藏——蜜蜂的秘密蜂蜜罐，里面装满了蜂蜜！他正开心地享用着新发现的宝藏，突然一只蜜蜂发现了他并拉响了警报。他知道，就在这一刻，成群的蜜蜂将从蜂巢中涌出，并开始四处扩散试图抓住他。他知道他必须离开蜂蜜罐并尽快回家，但蜂蜜实在太甜了，Mecho 不想太早离开。请帮助 Mecho 确定他能离开的最晚时间。

Mecho 的森林由一个 $N \times N$ 的单元格方格网表示，其边平行于南北和东西方向。每个单元格要么是树，要么是草地，要么是蜂巢，要么是 Mecho 的家。如果两个单元格在北、南、东或西方向上相邻（不包括对角线），则认为它们是相邻的。Mecho 是一只笨拙的熊，所以他每走一步都必须移动到相邻的单元格。Mecho 只能在草地上行走，不能穿过树木或蜂巢，并且他每分钟最多可以走 $S$ 步。

当蜂鸣警报响起时，Mecho 位于装有蜂蜜罐的草地单元格中，而蜜蜂位于每个装有蜂巢的单元格中（森林中可能不止一个蜂巢）。从这一刻起，每一分钟都会按以下顺序发生以下事件：

• 如果 Mecho 还在吃蜂蜜，他会决定是继续吃还是离开。如果他继续吃，他在这一整分钟内都不会移动。否则，他会立即离开，并按照上述描述在森林中走最多 $S$ 步。Mecho 不能带走任何蜂蜜，因此一旦他移动了，他就不能再吃蜂蜜了。
• 在 Mecho 吃完或移动完这一分钟后，蜜蜂会在网格上进一步扩散一个单位，仅移动到草地单元格中。具体来说，蜂群会扩散到任何与已包含蜜蜂的单元格相邻的草地单元格中。此外，一旦一个单元格包含蜜蜂，它将永远包含蜜蜂（也就是说，蜂群不会移动，但它会生长）。

换句话说，蜜蜂的扩散方式如下：当蜂鸣警报响起时，蜜蜂只占据蜂巢所在的单元格。第一分钟结束时，它们占据所有与蜂巢相邻的草地单元格（以及蜂巢本身）。第二分钟结束时，它们额外占据所有与“与蜂巢相邻的草地单元格”相邻的草地单元格，依此类推。如果有足够的时间，蜜蜂最终将同时占据森林中它们所能到达的所有草地单元格。

Mecho 和蜜蜂都不能走出森林。此外，请注意，根据上述规则，Mecho 吃蜂蜜的时间总是整数分钟。

如果 Mecho 在任何时间点发现自己处于被蜜蜂占据的单元格中，蜜蜂就会抓住他。

任务

编写一个程序，给定森林的地图，确定 Mecho 在初始位置继续吃蜂蜜的最大分钟数，同时仍能在他被蜜蜂抓住之前到达他的家。

数据范围

$1 \le N \le 800$ 地图的大小（边长） $1 \le S \le 1,000$ Mecho 每分钟最多可以走的步数

输入格式

程序必须从标准输入读取以下数据：

• 第一行包含整数 $N$ 和 $S$，由空格分隔。
• 接下来的 $N$ 行代表森林的地图。这些行中的每一行包含 $N$ 个字符，每个字符代表网格的一个单元格。可能的字符及其含义如下：
  • T 表示树
  • G 表示草地单元格
  • M 表示 Mecho 和蜂蜜罐的初始位置，这也是一个草地单元格
  • D 表示 Mecho 的家，Mecho 可以进入，但蜜蜂不能
  • H 表示蜂巢的位置

注意：保证地图中恰好包含一个字母 M，恰好一个字母 D，以及至少一个字母 H。还保证存在一条由相邻的 G 组成的路径连接 Mecho 到他的家，以及一条由相邻的 G 组成的路径连接至少一个蜂巢到蜂蜜罐（即 Mecho 的初始位置）。如果 Mecho 的家或蜂巢与 Mecho 的初始位置相邻，这些路径的长度可能为零。此外，请注意蜜蜂不能穿过或飞越 Mecho 的家。对它们来说，这就像一棵树。

输出格式

程序必须向标准输出写入一行，包含一个整数：Mecho 在初始位置继续吃蜂蜜的最大可能分钟数，同时仍能安全到家。

如果 Mecho 不可能在被蜜蜂抓住之前到达他的家，程序必须输出 -1。

子任务

对于部分测试用例，总分 40 分，满足 $N \le 60$。

样例

样例输入 1

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

样例输出 1

1

说明 1

吃了一分钟蜂蜜后，Mecho 可以直接沿最短路径向右走，再过两分钟他就能到家，避开蜜蜂。

样例输入 2

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

样例输出 2

2

说明 2

吃完两分钟蜂蜜后，Mecho 在第三分钟可以走 $\to\uparrow\to$，然后在第四分钟走 $\to\to\to$，在第五分钟走 $\downarrow\to$。