#include <bits/stdc++.h>
using namespace std;
int n,s,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},d[801][801],d2[801][801];
string m[801];
queue <pair <int, int>> q;
bool check(int x){
memset(d2,0,sizeof(d2));
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (m[i][j]=='M'){
q.push({i,j});
d2[i][j]=1;
}
while (!q.empty()){
auto [i,j]=q.front();
q.pop();
for (int k=0;k<4;k++){
int u=i+dx[k],v=j+dy[k];
if (min(u,v)>=0&&max(u,v)<n)
if (m[u][v]!='T'&&(d[u][v]-x*s>d2[i][j]||(d[u][v]-x*s>=d2[i][j]&&m[u][v]=='D'))&&!d2[u][v]){
d2[u][v]=d2[i][j]+1;
q.push({u,v});
}
}
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (m[i][j]=='D')
return d2[i][j];
}
int main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> s;
for (int i=0;i<n;i++){
cin >> m[i];
for (int j=0;j<n;j++)
if (m[i][j]=='H'){
q.push({i,j});
d[i][j]=1;
}
}
while (!q.empty()){
auto [i,j]=q.front();
q.pop();
for (int k=0;k<4;k++){
int u=i+dx[k],v=j+dy[k];
if (min(u,v)>=0&&max(u,v)<n)
if (m[u][v]!='T'&&!d[u][v]){
d[u][v]=d[i][j]+1;
q.push({u,v});
}
}
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
d[i][j]=(d[i][j]-1)*s;
int l=0,r=100000,kq=-1;
while (l<=r){
int mid=(l+r)>>1;
if (check(mid)){
kq=mid;
l=mid+1;
}
else
r=mid-1;
}
cout << kq;
}
