#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int n, s; cin >> n >> s;
vector<string> grid(n);
queue<pair<int, int>> q;
queue<int> qq;
pair<int, int> start;
for (int i = 0; i < n; ++i) {
cin >> grid[i];
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'H') {
q.push({i, j});
qq.push(0);
} else if (grid[i][j] == 'M') {
start = {i, j};
}
}
}
vector<vector<int>> whenbee(n, vector<int>(n, INT32_MAX));
while (!q.empty()) {
pair<int, int> loc = q.front();
int d = qq.front();
q.pop(); qq.pop();
if (loc.first < 0 || loc.first >= n || loc.second < 0 || loc.second >= n) continue;
if (grid[loc.first][loc.second] == 'T' || grid[loc.first][loc.second] == 'D') continue;
if (whenbee[loc.first][loc.second] != INT32_MAX) continue;
whenbee[loc.first][loc.second] = d;
q.push({loc.first - 1, loc.second});
q.push({loc.first + 1, loc.second});
q.push({loc.first, loc.second - 1});
q.push({loc.first, loc.second + 1});
for (int i = 0; i < 4; ++i) qq.push(d + 1);
}
auto works = [&whenbee, &n, &s, &grid, &start](int st) -> bool {
queue<pair<int, int>> q;
queue<int> qq;
q.push(start);
qq.push(st);
vector<vector<bool>> vis(n, vector<bool>(n));
while (!q.empty()) {
pair<int, int> loc = q.front();
int d = qq.front();
q.pop(); qq.pop();
if (loc.first < 0 || loc.first >= n || loc.second < 0 || loc.second >= n) continue;
if ((d / s) >= whenbee[loc.first][loc.second]) continue;
if (grid[loc.first][loc.second] == 'T') continue;
if (vis[loc.first][loc.second]) continue;
vis[loc.first][loc.second] = 1;
if (grid[loc.first][loc.second] == 'D') {
return 1;
}
q.push({loc.first - 1, loc.second});
q.push({loc.first + 1, loc.second});
q.push({loc.first, loc.second - 1});
q.push({loc.first, loc.second + 1});
for (int i = 0; i < 4; ++i) qq.push(d + 1);
}
return 0;
};
if (!works(0)) {
cout << "-1\n";
return 0;
}
int lo = 0, hi = n * n;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
if (works(s * mi)) {
lo = mi;
} else {
hi = mi - 1;
}
}
cout << lo << '\n';
return 0;
}
