#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define nl '\n'
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, S; cin >> N >> S;
vector<vector<char>> grid(N, vector<char> (N));
pair<int, int> Mecho, House;
vector<pair<int, int>> hives;
for (int a=0; a<N; a++) {
for (int b=0; b<N; b++) {
cin >> grid[a][b];
if (grid[a][b] == 'M') {
grid[a][b] = 'T';
Mecho = {a, b};
}
if (grid[a][b] == 'D') {
House = {a, b};
}
if (grid[a][b] == 'H') {
hives.pb({a, b});
}
}
}
int a=0, b = 1e9;
while(a <= b) {
int h = (a+b)/2;
vector<vector<int>> time(N, vector<int> (N));
vector<vector<bool>> used(N, vector<bool> (N)), usedMecho(N, vector<bool> (N));
deque<tuple<int, int, int>> q;
for (auto n: hives) {
q.pb({n.first, n.second, 0});
used[n.first][n.second] = 1;
}
bool mechoIn = 0;
while(!q.empty()) {
int x, y, isMecho;
tie(x, y, isMecho) = q.back();
q.pop_back();
vector<pair<int, int>> moves = {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
if (isMecho > S) {
q.push_front({x, y, 1});
usedMecho[x][y] = 1;
continue;
}
for (auto move: moves) {
if (move.first >= 0 && move.second >= 0 && move.first < N && move.second < N && grid[move.first][move.second] != 'T' && !used[move.first][move.second]) {
if (isMecho > 0 && isMecho - 1 < S && !usedMecho[move.first][move.second]) {
usedMecho[move.first][move.second] = 1;
q.push_back({move.first, move.second, isMecho+1});
} else if (grid[move.first][move.second] != 'D') {
time[move.first][move.second] = time[x][y] + 1;
if (!mechoIn && time[move.first][move.second] == h-1) {
mechoIn = 1;
q.push_front({Mecho.first, Mecho.second, 1});
usedMecho[Mecho.first][Mecho.second] = 1;
}
used[move.first][move.second] = 1;
q.push_front({move.first, move.second, 0});
}
}
}
}
// if (h == 2) {
// for (int e=0; e<N; e++) {
// for (int f=0; f<N; f++) {
// cout << usedMecho[e][f] << " ";
// }
// cout << nl;
// }
// cout << nl << nl;
// for (int e=0; e<N; e++) {
// for (int f=0; f<N; f++) {
// cout << used[e][f] << " ";
// }
// cout << nl;
// }
// }
// if (usedMecho[2][4]) {
// cout << h << nl << nl;
// for (int e=0; e<N; e++) {
// for (int f=0; f<N; f++) {
// cout << usedMecho[e][f] << " ";
// }
// cout << nl;
// }
// cout << nl << nl;
// for (int e=0; e<N; e++) {
// for (int f=0; f<N; f++) {
// cout << used[e][f] << " ";
// }
// cout << nl;
// }
// }
if (usedMecho[House.first][House.second]) {
a = h + 1;
} else b = h - 1;
}
cout << (b == -1 ? b: --b);
}
