#include <bits/stdc++.h>
using namespace std;
pair<int,int>inicio;
pair<int,int>final;
bool limites(int x, int y, int n){
if(x>=0&&x<n&&y>=0&&y<n){
return true;
}
else{
return false;
}
}
bool bfs(vector<vector<char>>&grid,vector<vector<int>>&bee, int &s, int n, int time){
vector<int>dx={1,0,-1,0};
vector<int>dy={0,1,0,-1};
vector<vector<int>>dist(n,vector<int>(n,-1));
dist[inicio.first][inicio.second]=0;
if((dist[inicio.first][inicio.second]+time)>bee[inicio.first][inicio.second]){
return false;
}
queue<pair<int,int>>cola;
cola.push({inicio});
while(!cola.empty()){
int x=cola.front().first;
int y=cola.front().second;
cola.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(limites(xx,yy,n)&&dist[xx][yy]==-1&&((ceil((dist[x][y]+1)/s)+time)<bee[xx][yy])&&grid[xx][yy]!='T'){
dist[xx][yy]=dist[x][y]+1;
cola.push({xx,yy});
}
}
}
if(dist[final.first][final.second]==-1){
return false;
}
else{
return true;
}
}
int main() {
int n,s;
cin>>n>>s;
vector<vector<char>>grid(n,vector<char>(n));
vector<pair<int,int>>abejas;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>grid[i][j];
if(grid[i][j]=='H'){
abejas.push_back({i,j});
}
else if(grid[i][j]=='M'){
inicio={i,j};
}
else if(grid[i][j]=='D'){
final={i,j};
}
}
}
vector<vector<int>>bee(n,vector<int>(n,INT_MAX));
queue<pair<int,int>>cola;
for(int i=0;i<abejas.size();i++){
cola.push(abejas[i]);
bee[abejas[i].first][abejas[i].second]=0;
}
vector<int>dx={1,0,-1,0};
vector<int>dy={0,1,0,-1};
while(!cola.empty()){
int x=cola.front().first;
int y=cola.front().second;
cola.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(limites(xx,yy,n)&&bee[xx][yy]==INT_MAX&&grid[xx][yy]!='T'&&grid[xx][yy]!='D'){
bee[xx][yy]=bee[x][y]+1;
cola.push({xx,yy});
}
}
}
if(!bfs(grid,bee,s,n,0)){
cout<<"-1\n";
return 0;
}
int l=0, r=1000000;
while(l<r){
int mid=(l+r+1)/2;
if(bfs(grid,bee,s,n,mid)){
l=mid;
}
else{
r=mid-1;
}
}
cout<<l<<"\n";
}
