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