#include <bits/stdc++.h>
#include <iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
const int sz=1005;
int n,s;
int d1[sz][sz];
int d0[sz][sz];
bool vis1[sz][sz];
bool vis0[sz][sz];
vector<pair<int,int>>hiv;
int px,py;
int dx,dy;
ll step[sz][sz];
int movex[4]={0,0,1,-1};
int movey[4]={-1,1,0,0};
char c[sz][sz];
void bfs(vector<pair<int,int>>&a,int d[sz][sz],bool visited[sz][sz]){
queue<pair<int,int>>q;
for (auto i:a){
q.push(i);
visited[i.first][i.second]=1;
}
while (!q.empty()){
int x1=q.front().first;
int y1=q.front().second;
q.pop();
for (int i=0;i<4;i++){
int x2=x1+movex[i];
int y2=y1+movey[i];
if (x2<0 or x2>=n) continue;
if (y2<0 or y2>=n) continue;
if (c[x2][y2]=='D' or c[x2][y2]=='T' or visited[x2][y2]) continue;
visited[x2][y2]=1;
d[x2][y2]=d[x1][y1]+1;
q.push({x2,y2});
}
}
}
bool bsearch(int k){
if (k==d0[px][py]) return 0;
for (int i=0;i<n;i++){
for(int j=0;j<n;j++){
vis1[i][j]=0;
d1[i][j]=0;
step[i][j]=INT_MAX;
}
}
queue<pair<int,int>>q;
q.push({px,py});
step[px][py]=k;
while (!q.empty()){
int sx=q.front().first;
int sy=q.front().second;
q.pop();
for (int i=0;i<4;i++){
int tx=sx+movex[i];
int ty=sy+movey[i];
if (tx<0 or tx>=n) continue;
if (ty<0 or ty>=n) continue;
if (c[tx][ty]=='H' or c[tx][ty]=='T' or vis1[tx][ty]) continue;
d1[tx][ty]=d1[sx][sy]+1;
int moves=k+d1[tx][ty]/s;
if (moves>=d0[tx][ty]) continue;
step[tx][ty]=moves+1;
vis1[tx][ty]=1;
q.push({tx,ty});
}
} for (int i=0;i<4;i++){
int tx=dx+movex[i];
int ty=dy+movey[i];
if (tx<0 or tx>=n or ty<0 or ty>=n or c[tx][ty]=='T' or c[tx][ty]=='H') continue;
if (step[tx][ty]<=d0[tx][ty]) return 1;
} return 0;
}
int main(){
cin>>n>>s;
for (int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>c[i][j];
if (c[i][j]=='D'){
dx=i;dy=j;
}
if (c[i][j]=='M'){
px=i;py=j;
} if (c[i][j]=='H'){
hiv.push_back({i,j});
}
}
}
bfs(hiv,d0,vis0);
int low=0;int high=1e9;
while (high>low){
int mid=low+(high-low+1)/2;
if (bsearch(mid)) low=mid;
else high=mid-1;
}
if (!bsearch(low)) cout <<-1;
else cout <<low;
}
