#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,one;
cin >> n >> one;
vector<string> s(n);
array<int,2> bear;
array<int,2> house;
vector<array<int,2>> bees;
for(int i=0;i<n;i++)
{
cin >> s[i];
for(int j=0;j<n;j++)
{
if(s[i][j]=='M') bear={i,j};
if(s[i][j]=='D') house={i,j};
if(s[i][j]=='H') bees.push_back({i,j});
}
}
auto in=[&](int r,int c)->bool{return (0<=r&&r<n&&0<=c&&c<n);};
vector<array<int,2>> z={{1,0},{-1,0},{0,-1},{0,1}};
int ltime=-1,rtime=n*n;
while(ltime<rtime-1)
{
int m=(ltime+rtime)/2;
queue<array<int,2>> qbees,qbear;
vector dbee(n,vector(n,int(-1)));
auto add_bee=[&](int r,int c,int nd)
{
if(in(r,c)&&s[r][c]!='T'&&s[r][c]!='D'&&dbee[r][c]==-1)
{
qbees.push({r,c});
dbee[r][c]=nd;
}
};
vector dbear(n,vector(n,int(-1)));
auto add_bear=[&](int r,int c,int nd)
{
if(in(r,c)&&s[r][c]!='T'&&dbee[r][c]==-1&&dbear[r][c]==-1)
{
qbear.push({r,c});
dbear[r][c]=nd;
}
};
for(auto [r,c]:bees) add_bee(r,c,0);
add_bear(bear[0],bear[1],0);
for(int i=0;!qbear.empty();i++)
{
while(!qbear.empty())
{
auto [r,c]=qbear.front();
int d=dbear[r][c];
if(d<(i-m+1)*one)
{
qbear.pop();
if(dbee[r][c]!=-1) continue;
for(auto [dr,dc]:z) add_bear(r+dr,c+dc,dbear[r][c]+1);
}
else break;
}
while(!qbees.empty())
{
auto [r,c]=qbees.front();
int d=dbee[r][c];
if(d<=i)
{
qbees.pop();
for(auto [dr,dc]:z) add_bee(r+dr,c+dc,dbee[r][c]+1);
}
else break;
}
}
if(dbear[house[0]][house[1]]!=-1) ltime=m;
else rtime=m;
}
cout << ltime << "\n";
return 0;
}
