#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
// https://oj.uz/problem/view/IOI09_mecho
const int MAX = 800;
char grid[MAX][MAX];
int n, s, dist[MAX][MAX],
dr[4] = {1, -1, 0, 0},
dc[4] = {0, 0, 1, -1};
pair<int, int> st, ed;
bool check(int mid) {
int trav[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
trav[i][j]=INT_MAX;
}
}
queue<pair<int, int>> q;
q.push(st);
//trav: 剩餘時間
trav[st.f][st.s]=mid*s;
while (!q.empty()) {
pair<int, int> p=q.front(); q.pop();
int r=p.f, c=p.s;
if (grid[r][c]=='D') {
return true;
}
for (int i=0; i<4; i++) {
int nr=r+dr[i], nc=c+dc[i];
if (nr>=0 && nr<n && nc>=0 && nc<n && grid[nr][nc]!='T' && trav[nr][nc]==INT_MAX){
trav[nr][nc]=trav[r][c]-1;
if (trav[nr][nc]>dist[nr][nc]) {
q.push({nr, nc});
}
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> s;
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
dist[i][j] = 2e9;
if (grid[i][j] == 'H') {
q.push({i, j});
dist[i][j] = 0;
} else if (grid[i][j] == 'M') {
st = {i, j};
} else if (grid[i][j] == 'D') {
ed = {i, j};
}
}
}
while (!q.empty()) {
auto p = q.front(); q.pop();
int r = p.f, c = p.s;
for (int i = 0; i < 4; i++) {
int r1 = r + dr[i], c1 = c + dc[i];
if (r1 >= 0 && r1 < n && c1 >= 0 && c1 < n
&& dist[r][c] + 1 < dist[r1][c1] &&
grid[r1][c1] != 'T' && grid[r1][c1] != 'D') {
dist[r1][c1] = dist[r][c] + 1;
q.push({r1, c1});
}
}
}
int low = 0, high = dist[st.f][st.s] - 1;
while (low < high) {
int mid = (low + high + 1) / 2;
if (check(mid)) {
low = mid;
} else {
high = mid - 1;
}
}
if (check(low)) cout << low << '\n';
else cout << -1 << '\n';
}
