#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, +1}};
int n, s;
char c[1000][1000];
int f[1000][1000];
pair<int, int> st, fi;
bool inside(pair<int, int> g) {
return (min(g.first, g.second) >= 0 && max(g.first, g.second) < n);
}
int t[1000][1000], step[1000][1000];
bool vis[1000][1000];
bool check(int T) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
step[i][j] = 0;
t[i][j] = INF;
vis[i][j] = false;
}
}
t[st.first][st.second] = T;
vis[st.first][st.second] = 1;
queue<pair<int, int>> q;
q.push(st);
while(!q.empty()) {
auto [x, y] = q.front();
q.pop();
if(c[x][y] == 'D') return 1;
if(t[x][y] > f[x][y] || (!step[x][y] && t[x][y] == f[x][y]))
continue;
for(auto [dx, dy] : dirs) {
pair<int, int> to = {x + dx, y + dy};
if(!inside(to) || vis[to.first][to.second]) continue;
vis[to.first][to.second] = true;
t[to.first][to.second] = t[x][y] + (step[x][y] == 0);
step[to.first][to.second] = (step[x][y] + 1) % s;
q.push(to);
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> s;
queue<pair<int, int>> h;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> c[i][j];
if(c[i][j] == 'H') {
h.push({i, j});
vis[i][j] = true;
}
if(c[i][j] == 'M')
st = {i, j};
if(c[i][j] == 'D') {
fi = {i, j};
vis[i][j] = true;
}
if(c[i][j] == 'T')
vis[i][j] = true;
}
}
while(!h.empty()) {
auto [x, y] = h.front();
h.pop();
for(auto [dx, dy] : dirs) {
pair<int, int> to = {x + dx, y + dy};
if(inside(to) && !vis[to.first][to.second]) {
vis[to.first][to.second] = true;
f[to.first][to.second] = f[x][y] + 1;
h.push(to);
}
}
}
int l = -1, r = 1e9;
while(r - l > 1) {
int m = (l + r) / 2;
if(check(m)) l = m;
else r = m;
}
cout << l;
}
