#include <iostream>
#include <queue>
using namespace std;
int const NMAX = 800;
char mat[1 + NMAX][1 + NMAX];
bool isBee[1 + NMAX][1 + NMAX];
bool isBear[1 + NMAX][1 + NMAX];
struct Point{
int x;
int y;
};
int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, -1, 0, 1};
bool isValid(Point to, int n) {
return (1 <= to.x && to.x <= n && 1 <= to.y && to.y <= n && mat[to.x][to.y] != 'T' && isBee[to.x][to.y] == false);
}
bool canBear(int n, int step, int delay) {
Point fin;
queue <Point> bear, bee;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
isBee[i][j] = isBear[i][j] = false;
if(mat[i][j] == 'D') {
fin = {i, j};
}
if(mat[i][j] == 'H') {
isBee[i][j] = true;
bee.push({i, j});
}
if(mat[i][j] == 'M') {
isBear[i][j] = true;
bear.push({i, j});
}
}
}
for(int s = 1;s <= delay;s++) {
int waveSize = bee.size();
for(int i = 1;i <= waveSize;i++) {
Point from = bee.front();
bee.pop();
for(int dir = 0;dir < 4;dir++) {
Point to = {from.x + dirX[dir], from.y + dirY[dir]};
if(isValid(to, n)) {
bee.push(to);
isBee[to.x][to.y] = true;
}
}
}
}
while(!bear.empty()) {
for(int s = 1;s <= step;s++) {
int waveSize = bear.size();
for(int i = 1;i <= waveSize;i++) {
Point from = bear.front();
bear.pop();
for(int dir = 0;dir < 4;dir++) {
Point to = {from.x + dirX[dir], from.y + dirY[dir]};
if(isValid(to, n) && !isBear[to.x][to.y]) {
bear.push(to);
isBear[to.x][to.y] = true;
}
}
}
}
int waveSize = bee.size();
for(int i = 1;i <= waveSize;i++) {
Point from = bee.front();
bee.pop();
for(int dir = 0;dir < 4;dir++) {
Point to = {from.x + dirX[dir], from.y + dirY[dir]};
if(isValid(to, n)) {
bee.push(to);
isBee[to.x][to.y] = true;
}
}
}
}
if(isBear[fin.x][fin.y] == true) {
return true;
}
return false;
}
int cautbin(int from, int to, int step, int n) {
if(from >= to) {
return from;
} else {
int mid = (from + to + 1) / 2;
if(canBear(n, step, mid)) {
return cautbin(mid, to, step, n);
}else {
return cautbin(from, mid-1, step, n);
}
}
}
int main() {
int n, step;
cin >> n >> step;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
cin >> mat[i][j];
}
}
int ans = cautbin(1, n*n, step, n);
if(canBear(n, step, ans)) {
cout << ans << '\n';
}else {
cout << "-1\n";
}
return 0;
}
