#include <bits/stdc++.h>
using namespace std;
int n, s, xini, yini, xfin, yfin;
bool visitado[802][802];
char a[802][802];
int abejas[802][802];
struct dato{
int x;
int y;
int tiempo;
};
int mov[4][2] = {{1,0}, {0,1}, {-1, 0}, {0, - 1}};
queue<dato> cola;
dato aux, nuevo;
void buscaA(){
while(!cola.empty()){
aux = cola.front();
cola.pop();
if(!visitado[aux.x][aux.y]){
if(aux.x > n || aux.x < 1 || aux.y > n || aux.y < 1 || a[aux.x][aux.y] == 'T' || a[aux.x][aux.y] == 'D'){
}else{
visitado[aux.x][aux.y] = true;
abejas[aux.x][aux.y] = aux.tiempo;
for(int i = 0; i < 4; ++i){
nuevo.tiempo = aux.tiempo + 1;
nuevo.x = aux.x + mov[i][0];
nuevo.y = aux.y + mov[i][1];
cola.push(nuevo);
}
}
}
}
}
struct oso{
int x;
int y;
int minutos;
int cont;
};
oso inicial, frenteO, nuevoO;
queue<oso> colaO;
bool visitadoOso[802][802];
bool valido(int t){
inicial.minutos = t;
inicial.x = xini;
inicial.y = yini;
inicial.cont = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
visitadoOso[i][j] = false;
}
}
colaO.push(inicial);
while(!colaO.empty()){
frenteO = colaO.front();
colaO.pop();
if(!visitadoOso[frenteO.x][frenteO.y]){
if(frenteO.x > n || frenteO.x < 1 || frenteO.y > n || frenteO.y < 1 || a[frenteO.x][frenteO.y] == 'T' || a[frenteO.x][frenteO.y] == 'H'){
}else{
if(frenteO.minutos < abejas[frenteO.x][frenteO.y] || (frenteO.x == xfin && frenteO.y == yfin)){
visitadoOso[frenteO.x][frenteO.y] = true;
for(int i = 0; i < 4; ++i){
nuevoO.cont = frenteO.cont + 1;
nuevoO.minutos = frenteO.minutos;
nuevoO.x = frenteO.x + mov[i][0];
nuevoO.y = frenteO.y + mov[i][1];
if(nuevoO.cont >= s){
nuevoO.cont = 0;
nuevoO.minutos++;
}
colaO.push(nuevoO);
}
}
}
}
}
if(visitadoOso[xfin][yfin]){
return true;
}
return false;
}
int bs(){
int inf = 0; int sup = n * n, medio, res = -1;
while(inf <= sup){
medio = (inf + sup) / 2;
if(valido(medio)){
res = medio;
inf = medio + 1;
}else{
sup = medio - 1;
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> s;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cin >> a[i][j];
if(a[i][j] == 'H'){
aux.x = i;
aux.y = j;
aux.tiempo = 0;
cola.push(aux);
}
if(a[i][j] == 'M'){
xini = i;
yini = j;
}
if(a[i][j] == 'D'){
xfin = i;
yfin = j;
}
}
}
buscaA();
cout << bs();
return 0;
}
