#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n,s;
cin>>n>>s;
vector<string> v(n);
for (int i=0;i<n;i++){
cin>>v[i];
}
int inf=(int)1e12;
vector<vector<int>> dis(n,vector<int>(n,inf));
queue<pair<int,int>> q;
pair<int,int> start={-1,-1};
pair<int,int> end={-1,-1};
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (v[i][j]=='H'){
q.push({i,j});
dis[i][j]=0;
}
if (v[i][j]=='M'){
start={i,j};
}
if (v[i][j]=='D'){
end={i,j};
}
}
}
auto valid = [&] (int x,int y){
return x>=0 && x<n && y>=0 && y<n;
};
vector<int> dx={0,-1,0,1};
vector<int> dy={-1,0,1,0};
while(!q.empty()){
auto [x,y]=q.front();
q.pop();
for (int i=0;i<4;i++){
if (valid(x+dx[i],y+dy[i]) && dis[x+dx[i]][y+dy[i]]==inf){
if (v[x+dx[i]][y+dy[i]]=='G'){
dis[x+dx[i]][y+dy[i]]=1+dis[x][y];
q.push({x+dx[i],y+dy[i]});
}
if (v[x+dx[i]][y+dy[i]]=='M'){
dis[x+dx[i]][y+dy[i]]=1+dis[x][y];
}
}
}
}
int low=0,high=inf;
int ans=-1;
while(low<=high){
int mid=(low+high)/2;
vector<vector<int>> dis2(n,vector<int>(n,inf));
q.push(start);
if (mid>=dis[start.first][start.second]){
q.pop();
}
dis2[start.first][start.second]=mid*s;
while(!q.empty()){
auto [x,y]=q.front();
q.pop();
for (int i=0;i<4;i++){
if (valid(x+dx[i],y+dy[i]) && v[x+dx[i]][y+dy[i]]!='T'){
if ((dis2[x][y]+1)/s<dis[x+dx[i]][y+dy[i]] && dis2[x+dx[i]][y+dy[i]]==inf){
dis2[x+dx[i]][y+dy[i]]=1+dis2[x][y];
q.push({x+dx[i],y+dy[i]});
}
}
}
}
if (dis2[end.first][end.second]==inf){
high=mid-1;
}
else{
ans=max(ans,mid);
low=mid+1;
}
}
cout<<ans<<"\n";
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
