#include <iostream>
#include <queue>
using namespace std;
const int N = 800;
int n, s, M, D, seen2[N * N], seen1[N * N];
char a[N][N];
vector<int> hiv;
queue<int> Q1, Q2, dmy;
bool valid(int i, int j){
return (i >= 0 and j >= 0 and i < n and j < n and a[i][j] != 'T');
}
void PushMecho(){
queue<int> Nw;
while (Q1.size() > 0){
int cur = Q1.front();
Q1.pop();
int i = cur / n, j = cur % n;
if (seen2[cur] == 1)
continue;
if (valid(i - 1, j) and seen2[cur - n] == 0 and seen1[cur - n] != 1)
seen1[cur - n] = 1, Nw.push(cur - n);
if (valid(i + 1, j) and seen2[cur + n] == 0 and seen1[cur + n] != 1)
seen1[cur + n] = 1, Nw.push(cur + n);
if (valid(i, j - 1) and seen2[cur - 1] == 0 and seen1[cur - 1] != 1)
seen1[cur - 1] = 1, Nw.push(cur - 1);
if (valid(i, j + 1) and seen2[cur + 1] == 0 and seen1[cur + 1] != 1)
seen1[cur + 1] = 1, Nw.push(cur + 1);
}
swap(Q1, Nw);
}
void PushBee(){
queue<int> Nw;
while (Q2.size() > 0){
int cur = Q2.front();
Q2.pop();
int i = cur / n, j = cur % n;
if (valid(i - 1, j) and cur - n != D and seen2[cur - n] != 1)
seen2[cur - n] = 1, Nw.push(cur - n);
if (valid(i + 1, j) and cur + n != D and seen2[cur + n] != 1)
seen2[cur + n] = 1, Nw.push(cur + n);
if (valid(i, j - 1) and cur - 1 != D and seen2[cur - 1] != 1)
seen2[cur - 1] = 1, Nw.push(cur - 1);
if (valid(i, j + 1) and cur + 1 != D and seen2[cur + 1] != 1)
seen2[cur + 1] = 1, Nw.push(cur + 1);
}
swap(Q2, Nw);
}
bool canHeReachAfter(int l){
for (int i=0;i<n*n;i++)
seen1[i] = seen2[i] = 0;
Q1 = dmy, Q2 = dmy;
for (int i : hiv)
Q2.push(i), seen2[i] = 1;
Q1.push(M), seen1[M] = 1;
while (l > 0)
PushBee(), l--;
while (Q1.size() > 0){
for (int i=0;i<s and Q1.size() > 0;i++)
PushMecho();
PushBee();
}
return seen1[D];
}
signed main(){
cin>>n>>s;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
cin>>a[i][j];
if (a[i][j] == 'M')
M = i * n + j;
if (a[i][j] == 'D')
D = i * n + j;
if (a[i][j] == 'H')
hiv.push_back(i * n + j);
}
}
int l = -1, r = n * n + 1;
while (l + 1 < r){
int mid = (l + r) / 2;
if (canHeReachAfter(mid))
l = mid;
else
r = mid;
}
cout<<l<<'\n';
}
