#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,s;
cin>>n>>s;
auto a=vector(n,vector<char>(n));
int mi,mj,di,dj;
vector<pair<int,int>>h;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
if(a[i][j]=='D'){
di=i,dj=j;
}
if(a[i][j]=='M'){
mi=i,mj=j;
}
if(a[i][j]=='H'){
h.pb({i,j});
}
}
}
vector<int>dx={0,0,-1,1};
vector<int>dy={-1,1,0,0};
auto bee=vector(n,vector<int>(n,1e9));
queue<pair<int,int>>q;
for(auto [i,j]:h){
bee[i][j]=0;
q.push({i,j});
}
vector<pair<int,int>>g[n*n];
while(!q.empty()){
int i=q.front().ff,j=q.front().ss;
int d=bee[i][j];
q.pop();
for(int k=0;k<4;k++){
int ni=i+dx[k],nj=j+dy[k];
if(ni<0||nj<0||ni>=n||nj>=n) continue;
if(a[ni][nj]=='T'||a[ni][nj]=='D') continue;
if(bee[i][j]+1<bee[ni][nj]){
bee[ni][nj]=bee[i][j]+1;
q.push({ni,nj});
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(bee[i][j]<1e9){
g[bee[i][j]].pb({i,j});
}
}
}
int lo=-1,hi=n*n;
vector<bool>used(n*n,false);
while(lo<hi){
int mid=(lo+hi+1)/2;
auto dist=vector(n,vector<int>(n,1e9));
queue<pair<int,int>>q;
q.push({mi,mj});
dist[mi][mj]=mid;
int cur=0;
bool ok=false;
fill(all(used),false);
while(!q.empty()){
int i=q.front().ff,j=q.front().ss;
int d=dist[i][j];
if((d-mid)/s+mid>=bee[i][j]){
q.pop();
continue;
}
if(i==di&&j==dj){
ok=true;
break;
}
q.pop();
for(int k=0;k<4;k++){
int ni=i+dx[k],nj=j+dy[k];
if(ni<0||nj<0||ni>=n||nj>=n) continue;
if(a[ni][nj]=='T') continue;
if(dist[i][j]+1<dist[ni][nj]){
dist[ni][nj]=dist[i][j]+1;
q.push({ni,nj});
}
}
}
if(ok) lo=mid;
else hi=mid-1;
}
cout<<lo;
return 0;
}
