// Author: Teoman Ata Korkmaz
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
constexpr int N=888;
///////////////////////////////////////////////////////////
int n,k,t[N][N];
bool vis[N][N];
pair<int,int> startpoint;
string s[N];
inline void bfs(){
memset(t,-1,sizeof(t));
queue<pair<int,int>> q;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(s[i][j]=='H'){
q.push({i,j});
t[i][j]=0;
}
}
}
while(q.size()){
auto [i,j]=q.front();q.pop();
// cerr<<"i,j: "<<i<<" "<<j<<endl;
if(i>0 && t[i-1][j]==-1 && (s[i-1][j]=='G' || s[i-1][j]=='M')) t[i-1][j]=t[i][j]+1, q.push({i-1,j});
if(i<n-1 && t[i+1][j]==-1 && (s[i+1][j]=='G' || s[i+1][j]=='M')) t[i+1][j]=t[i][j]+1, q.push({i+1,j});
if(j>0 && t[i][j-1]==-1 && (s[i][j-1]=='G' || s[i][j-1]=='M')) t[i][j-1]=t[i][j]+1, q.push({i,j-1});
if(j<n-1 && t[i][j+1]==-1 && (s[i][j+1]=='G' || s[i][j+1]=='M')) t[i][j+1]=t[i][j]+1, q.push({i,j+1});
}
}
inline bool f(int x){
// cerr<<"f: "<<x<<endl;
memset(vis,0,sizeof(vis));
queue<pair<int,pair<int,int>>> q;
q.push({0,startpoint});
while(q.size()){
int d=q.front().first;
int i=q.front().second.first;
int j=q.front().second.second;
q.pop();
// cerr<<"d,i,j: "<<d<<" "<<i<<" "<<j<<endl;
// if(i==3 && j==6)cerr<<"here: "<<d<<endl;
if(vis[i][j])continue;
// if(i==3 && j==6)cerr<<"here: "<<d<<endl;
if(s[i][j]=='D')return true;
// if(i==3 && j==6)cerr<<"here: "<<d<<endl;
if(x+d/k>=t[i][j])continue;
// if(i==3 && j==6)cerr<<"here: "<<d<<endl;
if(s[i][j]=='T')continue;
// if(i==3 && j==6)cerr<<"here: "<<d<<endl;
if(s[i][j]=='H')continue;
// if(i==3 && j==6)cerr<<"here: "<<d<<endl;
vis[i][j]=true;
if(i>0 ) q.push({d+1,{i-1,j}});
if(i<n-1) q.push({d+1,{i+1,j}});
if(j>0 ) q.push({d+1,{i,j-1}});
if(j<n-1) q.push({d+1,{i,j+1}});
}
return false;
}
signed main(void){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++){
bool flag=false;
for(int j=0;j<n;j++){
if(s[i][j]=='M'){
startpoint={i,j};
s[i][j]='G';
flag=true;
break;
}
}
if(flag)break;
}
bfs();
// for(int i=0;i<n;i++){
// cerr<<"t:";
// for(int j=0;j<n;j++){
// cerr<<" "<<t[i][j];
// }
// cerr<<endl;
// }
// cerr<<endl;
int l=0,r=1e5;
while(l<r){
int m=(l+r)>>1;
if(f(m))l=m+1;
else r=m;
}
cout<<l-1<<endl;
}
/*
t: -1 -1 -1 -1 -1 -1 -1
t: -1 6 5 5 6 7 -1
t: -1 5 4 4 5 6 -1
t: 5 4 3 3 4 5 -1
t: -1 3 2 2 3 4 -1
t: -1 2 1 1 2 3 -1
t: -1 1 0 0 1 2 -1
*/
