[IOI 2009] Mecho

小熊 Mecho 发现了一个宝藏 —— 蜜蜂的秘密蜜罐，里面装满了蜂蜜！他高兴地吃着他的新发现的宝藏，直到突然有一只蜜蜂看到了他，并发出了警报。他知道就在这个时刻，成群的蜜蜂会从蜂巢里出来，开始四处蔓延，试图抓住他。他知道他必须离开蜜罐，尽快回家，但蜂蜜太甜了， Mecho 不想太早离开。帮 Mecho 确定他最晚什么时候可以离开。 Mecho 所在的森林是 $N\times N$ 的正方形网格，其两侧平行于南北和东西方向。每个格子由一棵树、一小块草、一个蜂巢或 Mecho 的家占据。如果两个格子中的一个与另一个的北、南、东或西相邻（但不在对角线上），则认为这两个格子相邻。Mecho 是一只笨拙的熊，所以每次它走一步，都只能移动至相邻的格子。Mecho 只能在草地上行走，不能穿过树木或蜂巢，而且他每分钟最多能走 $S$ 步。 当蜜蜂警报响起的那一刻， Mecho 在装有蜜罐的草格子里，而蜜蜂则在每个包含蜂巢的格子里（森林里可能有不止一个蜂巢）。接下来的每一分钟内，以下事件按顺序发生: 1. 如果 Mecho 还在吃蜂蜜，他会决定是继续吃还是离开。如果它继续吃东西，就会一动不动。否则，他会立即离开，并像上面描述的那样移动至多 $S$ 步。 Mecho 不能带任何蜂蜜，所以一旦他移动了，他就不能再吃蜂蜜了。 2. 当 Mecho 吃完或移动了整整一分钟后，蜜蜂在网格中进一步扩散了一个单位，只移动到草格子中。具体地，蜂群扩散到每一个与任何已经有蜜蜂的格子相邻的草格子。此外，一旦一个格子有蜜蜂，它将永远有蜜蜂（也就是说，蜂群不移动，但它生长）。 换句话说，蜜蜂的分布如下：当蜜蜂警报响起时，蜜蜂只占据蜂巢所在的格子。在第一分钟结束时，它们占据了蜂巢附近所有长满草的格子（以及原本的所有蜂巢）。在第二分钟结束时，它们又占据了和 “与蜂巢相邻的草格子” 相邻的草格子，以此类推。只要有足够的时间，这些蜜蜂就会同时占据森林中它们能到达的所有草格子。 Mecho 和蜜蜂都不能走出森林。另外，根据上面的规则，Mecho 总是吃整数分钟的蜂蜜。 如果 Mecho 发现自己在一个被蜜蜂占据的格子里，蜜蜂就会抓住 Mecho。 **任务**：编写一个程序，给定一张森林地图，计算出 Mecho 可以在最初的位置继续吃蜂蜜的最长时间，同时还能在任何蜜蜂抓到他之前回到他的家。 ## Input 第一行包含两个由空格隔开的整数 $N, S$，分别表示地图大小和 Mecho 每分钟最多移动的步数。 接下来 $N$ 行描述了森林地图。其中每一行包含 $N$ 个字符，每个字符表示一个格子。可能的字符及其含义如下: - `T` 表示树。 - `G` 表示草格子。 - `M` 表示 Mecho 的初始位置，也是蜜罐的位置。这是一个草格子，蜜蜂可以进入。 - `D` 表示 Mecho 的家。Mecho 可以进入这个格子，但蜜蜂不可以。 - `H` 表示蜂巢。 **注意**：保证地图恰好包含一个字母 `M`，恰好一个字母 `D` 和至少一个字母 `H`。保证存在相邻的字母 `G` 形成的路径连接 Mecho 和它的家，以及相邻的字母 `G` 形成的路径连接蜜罐（即 Mecho 最初的位置）和至少一个蜂巢。这些序列可能长度为零，如 Mecho 的家或蜂巢和 Mecho 的初始位置相邻。另外，蜜蜂不能通过或飞过 Mecho 的家。对它们来说，Mecho 的家就像一棵树。 ## Output 输出一行一个整数，表示 Mecho 最多还能在初始位置吃多少分钟蜂蜜，并安全地回家。 如果 Mecho 不可能在蜜蜂抓住它之前回家，输出 $-1$。 [samples] ## Background IOI2009 D2T2 ## Note ### 样例解释 - 样例 1：吃了一分钟蜂蜜后，Mecho 可以沿着最短的路径直接往右走，再过两分钟他就可以安全到家了。 - 样例 2：吃了两分钟蜂蜜后，Mecho 可以在第三分钟向右，向上，向右走；在第四分钟向右走三步；在第五分钟向下，向右走。 ### 数据范围与约定 - 对于 $40\%$ 的数据，$N\leq 60$。 - 对于 $100\%$ 的数据，$1\leq N\leq 800$，$1\leq S\leq 1000$。 注意在实际评测中，部分分和以上描述有出入。