#include <bits/stdc++.h>
using namespace std;
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
int dir[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
signed main(){
int n,s;cin>>n>>s;
char mat[n][n];
int sx,sy,ex,ey;
queue<pair<int,int>> lol;
vector<vector<int>> ft(n, vector<int>(n, 1e9));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>mat[i][j];
if(mat[i][j]=='M'){
sx=i,sy=j;
}
else if(mat[i][j]=='H'){
lol.push({i,j});
ft[i][j]=0;
}
else if(mat[i][j]=='D'){
ex=i,ey=j;
}
}
}
while(!lol.empty()){
auto [x,y]=lol.front();lol.pop();
for(int i=0;i<4;i++){
int nx=x+dir[i][0], ny=y+dir[i][1];
if(nx < 0 or nx >= n or ny <0 or ny>=n or mat[nx][ny]=='D' or mat[nx][ny]=='T' or
ft[nx][ny] < 1e9)continue;
ft[nx][ny]=ft[x][y]+1;
lol.push({nx,ny});
}
}
int l=-1, r=800000, m;
while(l<r-1){
m=(l+r)/2;
vector<vector<int>> dist(n, vector<int>(n, 1e9));
dist[sx][sy]=0;
queue<pair<int,int>> q;
q.push({sx,sy});
//~ printf("m is %lld\n", m);
while(!q.empty()){
auto [x,y]=q.front();q.pop();
for(int i=0;i<4;i++){
int nx=x+dir[i][0], ny=y+dir[i][1], nd=dist[x][y]+1;
if(nx < 0 or nx >= n or ny <0 or ny>=n or
mat[nx][ny]=='T' or m+nd/s>=ft[nx][ny] or dist[nx][ny] < 1e9)continue;
//~ printf("going to %lld %lld, dist is nd %lld, m + nd/s is %lld, ft is %lld\n", x, y, nd, m+nd/s,ft[nx][ny]);
dist[nx][ny]=nd;
q.push({nx,ny});
}
}
if(dist[ex][ey] < 1e9)l=m;
else r=m;
}
cout<<l;
}
