1953: 无敌狗仔

和hyf不同，Will很低调的，自从上次表白成功追到了SuperPPMM之后，Will那是相当相当低调――约会也是。不过，这次Will的传统理念算是被颠覆了……

Will和PPMM正在浪漫的约会呢，Will猛然得到最新消息，有若干狗仔团队正闻讯蜂拥而来（Will毕竟还是蛮有名气的嘛）……

Will真是不理解现在这些人对八卦的渴望怎么那么大，连保密工作做的这么好的Will都未能幸免，这真是……

算了，别扯了，先溜吧，被狗仔队逮到可不好，但是，今天晚上和PPMM的浪漫约会Will真不想撤，那么就能呆多久呆多久吧，Will希望在不会被抓的前提下和MM呆尽量久的时间。

城市可以看做是N行N列的方格，每一个格子会是一个建筑物，一片空地，一个狗仔队的窝点，或者是Will的家。我们认为两个格子如果有相同的边，那么就是相邻的。城市里居民都是良民，每次走的时候，只会走相邻的格子。显然的，私闯民宅可不好，所以不论是谁都不会闯到建筑物里的……由于要保护MM， Will每一秒至多走S步，S可能很大，因为这是爱情的力量！

当Will得知狗仔队将至的消息时，Will在和MM约会，而狗仔队都在各自窝点。随着时间的前进，每一秒都会按照如下的顺序发生着一些事件：

*) 如果Will还在约会地点，那么他可以选择现在这一秒是和MM浪漫，还是开始逃跑――如果是继续浪漫，那么这一秒Will是不会移动的，如果逃跑，那么接下来Will可以在城市里移动不超过S步――当然的，开始逃跑了怎么还会有心思浪漫呢？所以一旦离开了，Will就会保护着MM一直不停的逃跑。当然了，如果在某个位置遇到了狗仔队，那么可怜的Will就要悲剧了……

*) 当Will决定或者移动完毕之后，所有的狗仔队会向四周更远的格子移动一步――当然，也只会走到空地上，并且最邪恶的是一旦狗仔队走到了一个格子，就会派一个狗仔留守在那里――或者可以这么说，如果格子a和b是相邻的空地，并且在前一秒狗仔队占据了格子a，那么这一秒过后，a和b都将被狗仔队占据。最开始的时候，狗仔队占据了所有狗仔窝点所在的格子。

狗仔和Will都不能走出城市。并且，显然的，根据规则，Will继续和MM浪漫的时间，必然是一个整数秒。

狗仔队是无法占领Will的家的，所以Will只要回到家里就安全啦！现在Will想知道如果要能够安全回到家，那么最多他还能和MM浪漫多长时间呢？

第一行两个整数，N，S

接下来N行每行N个字符描述每个格子的具体情况

T 这个格子是一个建筑物

G 这是一块空地

M 这是Will和MM浪漫的地方，当然也是个空地

D 这是Will的家

H 这是一个狗仔队的窝点

一行一个整数，表示Will最多还能和MM浪漫多长时间，如果Will不可能回到家了，那么就输出-1，否则显然答案是非负整数。

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

1