#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define int ll
const int N=801;
char g[N][N];
int dist[N][N];
int d[N][N];
int sx,sy,n,s,hy,hx;
vector<pair<int,int>> hives;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
void bfs()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
dist[i][j]=1e18;
}
}
queue<pair<int,int>> q;
for(auto co:hives)
{
q.push(co);
dist[co.first][co.second]=0;
}
while(q.size())
{
auto it=q.front();
q.pop();
int x=it.first;
int y=it.second;
// cout<<"Dist "<<x<<' '<<y<<' '<<dist[x][y]<<endl;
for(int i=0;i<4;i++)
{
int nx=it.first+dx[i],ny=it.second+dy[i];
if(nx>=0 and nx<n and ny>=0 and ny<n and g[nx][ny]!='T' and g[nx][ny]!='D') // bees can pass his home and trees
{
if(dist[nx][ny]>dist[x][y]+s)
{
dist[nx][ny]=dist[x][y]+s;
q.push({nx,ny});
}
}
}
}
// int x=hx,y=hy;
// for(int i=0;i<4;i++)
// {
// int nx=x+dx[i],ny=y+dy[i];
// if(nx>=0 and nx<n and ny>=0 and ny<n and g[nx][ny]!='T') // bees can pass his home and trees
// {
// if(dist[nx][ny]+s<dist[x][y])
// {
// dist[x][y]=dist[nx][ny]+s;
// }
// }
// }
}
bool check(int tm)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
d[i][j]=1e18;
}
}
// dist[sx][sy] - dt[sx][sy] for all sx ,sy and then get maximum minimum by binary search
// {min(ti-i),cur_time} we want to maximize min(ti-i) as first priority and minimize cur_time as second priority
// we maximize -cur_time
d[sx][sy]=tm;
queue<pair<int,int>> q;
q.push({sx,sy});
while(q.size())
{
auto it=q.front();
q.pop();
int x=it.first;
int y=it.second;
// cout<<"For "<<x<<' '<<y<<' '<<d[x][y]<<' '<<dist[x][y]<<endl;
// // bees can reach the point with us or before then we are cooked
if(d[x][y]>=dist[x][y])continue;
for(int i=0;i<4;i++)
{
int nx=it.first+dx[i],ny=it.second+dy[i];
if(nx>=0 and nx<n and ny>=0 and ny<n and g[nx][ny]!='T') // bear can go throguth tree
{
if(d[nx][ny]>d[x][y]+1)
{
d[nx][ny]=d[x][y]+1;
q.push({nx,ny});
}
}
}
}
return d[hx][hy]!=1e18; // we can reach it thus meaning we won as bees can reach our home
}
int32_t main()
{
cin>>n>>s;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>g[i][j];
if(g[i][j]=='M')
{
sx=i,sy=j;
}
if(g[i][j]=='D')
{
hx=i,hy=j;
}
if(g[i][j]=='H')
{
hives.push_back({i,j});
}
}
}
bfs();
int l=-1,r=1e9+10;
while(l+1<r)
{
ll mid=(l+r)/2;
// cout<<"Checking for "<<mid*s<<endl;
if(check(mid*s))
{
l=mid;
}
else
{
r=mid;
}
}
cout<<l<<endl;
}
