#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fs first
#define sc second
#define pb push_back
const int N=810;
char a[N][N],g[N*N];
vector<int> v[N*N];
int fix[N*N],t[N*N],n,s,fix2[N*N],t2[N*N],st,en;
int check(int mid ){
for(int i=1; i<=n*n; i++){
t2[i]=1e18;
fix[i]=0;
}
deque<int> deq;
fix[st]=1;
t2[st]=mid;
if(t2[st]<t[st]){
deq.pb(st);
}
while(!deq.empty()){
int to=deq.front();
deq.pop_front();
for(int i=0; i<v[to].size(); i++){
int to1=v[to][i];
if(g[to1]=='D'){
return 1;
}
if(fix[to1]==1 or t[to1]<=min(t2[to1],t2[to]+1) or g[to1]=='H'){
continue;
}
t2[to1]=min(t2[to1],t2[to]+1);
deq.pb(to1);
fix[to1]=1;
}
}
// for(int i=1; i<=n; i++){
// for(int j=1; j<=n; j++){
// cout<<t2[(i-1)*n+j]<<" ";
// }
// cout<<endl;
// }
return -1;
}
void bfs (){
deque<int> deq;
for(int i=1; i<=n*n; i++){
if(g[i]=='H'){
deq.pb(i);
fix[i]=1;
t[i]=0;
}
}
while(!deq.empty()){
int to=deq.front();
deq.pop_front();
for(int i=0; i<v[to].size(); i++){
int to1=v[to][i];
if(fix[to1]==1 or g[to1]=='D'){
continue;
}
t[to1]=min(t[to1],t[to]+s);
deq.pb(to1);
fix[to1]=1;
}
}
}
signed main(){
cin>>n>>s;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin>>a[i][j];
g[(i-1)*n+j]=a[i][j];
}
}
for(int i=1; i<=n*n; i++){
t[i]=1e18;
t2[i]=1e18;
if(g[i]=='M'){
st=i;
}
if(g[i]=='D'){
en=i;
}
}
for(int i=1; i<=n*n; i++){
if(g[i]=='T')continue;
if(i+1>=1 and i+1<=n*n){
if(g[i]!='T' and g[i+1]!='T' and i%n!=0){
v[i].pb(i+1);
v[i+1].pb(i);
}
}
if(i+n<=n*n and i+n>=1 ){
if(g[i+n]!='T' and g[i]!='T'){
v[i].pb(i+n);
v[i+n].pb(i);
}
}
}
bfs();
if(check(0)==-1){
cout<<-1<<endl;
return 0;
}
int l=0;
int r=n*n;
int ans=0;
// for(int i=1; i<=n; i++){
// for(int j=1; j<=n; j++){
// cout<<t[(i-1)*n+j]<<" ";
// }
// cout<<endl;
// }
while(l<=r){
int mid=(l+r)/2;
if(check(mid*s)!=-1){
l=mid+1;
ans=max(mid,ans);
}
else{
r=mid-1;
}
}
cout<<ans<<endl;
}
