#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
/*
MC lover
*/
const int maxN=800;
char lab[maxN+1][maxN+1];
int dis[maxN+1][maxN+1], vm[maxN+1][maxN+1];
int dirX[]={1, 0, -1, 0};
int dirY[]={0, 1, 0, -1};
void solve(){
int n, s; cin>>n>>s;
queue<pair<int, int>>mulbfs;
auto in=[&](int x, int y){
return x>=0 && y>=0 && x<n && y<n;
};
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<n ; j++){
dis[i][j]=1e9;
cin>>lab[i][j];
if(lab[i][j]=='H'){
mulbfs.push({i, j});
dis[i][j]=0;
// dbg(i)
// dbg(j)
}
}
}
int ans=-1;
while(!mulbfs.empty()){
pair<int, int>x=mulbfs.front();
// cout<<x.first<<" "<<x.second<<"\n";
mulbfs.pop();
for(int k=0 ; k<4 ; k++){
int xx=x.first+dirX[k], yy=x.second+dirY[k];
if(!in(xx, yy)) continue;
// dbg(xx)
// dbg(yy)
if(dis[xx][yy]==1e9 && lab[xx][yy]!='T'){
dis[xx][yy]=dis[x.first][x.second]+1;
mulbfs.push({xx, yy});
}
}
}
int l=0, r=(n+1)*(n+1);
while(l<=r){
int mid=(l+r)/2;
// mid=2;
pair<int, int>start, end;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<n ; j++){
vm[i][j]=1e9;
// cout<<dis[i][j]<<" ";
if(lab[i][j]=='M') start={i, j};
if(lab[i][j]=='D') end={i, j};
}
// cout<<"\n";
}
// cout<<"\n";
vm[start.first][start.second]=0;
queue<pair<int, int>>bfs;
bfs.push(start);
while(!bfs.empty()){
pair<int, int>x=bfs.front();
bfs.pop();
for(int k=0 ; k<4 ; k++){
int xx=x.first+dirX[k], yy=x.second+dirY[k];
if(!in(xx, yy)) continue;
// dbg(xx)
// dbg(yy)
if(vm[xx][yy]==1e9 && lab[xx][yy]!='T' && dis[xx][yy]>=(((vm[x.first][x.second])+s)/s)+mid){
vm[xx][yy]=vm[x.first][x.second]+1;
bfs.push({xx, yy});
}
}
}
// for(int i=0 ; i<n ; i++){
// for(int j=0 ; j<n ; j++) cout<<vm[i][j]<<" ";
// cout<<"\n";
// }
// dbg(vm[end.first][end.second])
if(vm[end.first][end.second]==1e9) r=mid-1;
else{
l=mid+1;
ans=mid;
}
// break;
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
