#include<bits/stdc++.h>
using namespace std;
#define int long long int
int n,speed;
char inp[805][805];
int board[805][805];
bool visited[805][805];
queue<pair<int,int>> q;
pair<int,int> s,e;
int cr,cc,er,ec;
int dr[]={0,-1,0,1};
int dc[]={1,0,-1,0};
int maxTime=0;
int l,m,r;
int layer,tillNext,inNext;
bool bfs(int start)
{
queue<pair<int,int>> tempq;
memset(visited,0,sizeof(visited));
int time=start;
tempq.push({s.first,s.second});
tillNext=1;
inNext=0;
layer=0;
while(!tempq.empty())
{
cr = tempq.front().first;
cc = tempq.front().second;
tempq.pop();
if(board[cr][cc]>time or inp[cr][cc]=='M')//bees have not reached this spot yet
{
//cout << time;
for(int i=0;i<4;i++)
{
er = cr + dr[i];
ec = cc + dc[i];
if(er<0 or ec<0 or er>=n or ec>=n) continue;
if(inp[er][ec]=='D') return 1;
if(visited[er][ec]) continue;
if(board[er][ec]==-1) continue;
if(board[er][ec]<=time) continue;
tempq.push({er,ec});
visited[er][ec]=1;
inNext++;
}
}
tillNext--;
if(tillNext==0)
{
tillNext = inNext;
inNext = 0;
layer++;
if(layer%speed==0) time++;
}
}
return 0;
}
int32_t main()
{
cin.tie(0); ios_base::sync_with_stdio(false);
cin >> n >> speed;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin >> inp[i][j];
if(inp[i][j]=='T') board[i][j]=-1; //no one can traverse
if(inp[i][j]=='H')
{
board[i][j]=0; //not walkable since the 0th sec
q.push({i,j});
}
if(inp[i][j]=='M') s={i,j};
if(inp[i][j]=='D') e={i,j};
if(inp[i][j]=='G') board[i][j] = 1000000;
}
}
//bees
while(!q.empty())
{
cr = q.front().first;
cc = q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
er = cr + dr[i];
ec = cc + dc[i];
if(er<0 or ec<0 or er>=n or ec>=n) continue;
if(board[er][ec]==-1 or board[er][ec]=='D' or board[er][ec]=='M') continue;
if(board[er][ec]<=board[cr][cc]+1) continue;
board[er][ec]=board[cr][cc]+1;
q.push({er,ec});
maxTime=max(maxTime,board[er][ec]);
}
}
l=0;
r=maxTime;
m = l + (r-l)/2;
int best=-1;
while(l<=r)
{
//cout << l << ' ' << r << ' ' << m << '\n';
if(bfs(m)==1)
{
l=m+1;
best = max(best,m);
}
else r=m-1;
m = l + (r+0.5-l)/2;
}
if(m==0 and bfs(0)==0) cout << -1;
else cout << max(best,m);
}
