#include<bits/stdc++.h>
using namespace std;
#define int long long
std::vector<vector<int>>map;
std::vector<vector<int>>Time;
bool CheckPossible(int ST,int s,pair<int,int> Start,vector<vector<int>> Time,int n){
std::queue<pair<pair<int,int>,int>>Expand;
if(Time[Start.first][Start.second]<=ST){
return false;
}
Expand.push({{Start.first,Start.second},0});
while(!Expand.empty()){
int x=Expand.front().first.first;
int y=Expand.front().first.second;
int t=Expand.front().second;
if(x>0 && Time[x-1][y]>ST+((t+1)/s)){
Expand.push({{x-1,y},t+1});
}
if(x<n-1 && Time[x+1][y]>ST+((t+1)/s)){
Expand.push({{x+1,y},t+1});
}
if(y>0 && Time[x][y-1]>ST+((t+1)/s)){
Expand.push({{x,y-1},t+1});
}
if(y<n-1 && Time[x][y+1]>ST+((t+1)/s)){
Expand.push({{x,y+1},t+1});
}
if(Time[x][y]==100000){
return true;
}
Time[x][y]=-1;
Expand.pop();
}
return false;
}
signed main(){
int n,s;
cin>>n>>s;
pair<int,int> start;
Time=vector<vector<int>>(n,vector<int>(n,-1));
std::queue<pair<pair<int,int>,int>>Expand;
for(int x=0;x<n;x++){
for(int y=0;y<n;y++){
char c;
cin>>c;
if(c=='T'){
Time[x][y]=0;
}
if(c=='M'){
start={x,y};
}
if(c=='D'){
Time[x][y]=100000;
}
if(c=='H'){
Time[x][y]=0;
Expand.push({{x,y},0});
}
}
}
while(!Expand.empty()){
int x=Expand.front().first.first;
int y=Expand.front().first.second;
int t=Expand.front().second;
if(x>0 && Time[x-1][y]==-1){
Time[x-1][y]=t+1;
Expand.push({{x-1,y},t+1});
}
if(x<n-1 && Time[x+1][y]==-1){
Time[x+1][y]=t+1;
Expand.push({{x+1,y},t+1});
}
if(y>0 && Time[x][y-1]==-1){
Time[x][y-1]=t+1;
Expand.push({{x,y-1},t+1});
}
if(y<n-1 && Time[x][y+1]==-1){
Time[x][y+1]=t+1;
Expand.push({{x,y+1},t+1});
}
Expand.pop();
}
if(!CheckPossible(0,s,start,Time,n)){
cout<<-1<<endl;
return 0;
}
int min=0;
int max=1000;
while(min<max){
int m=(min+max-1)/2+1;
if(CheckPossible(m,s,start,Time,n)){
min=m;
}else{
max=m-1;
}
}
cout<<min<<endl;
return 0;
}
