#include <bits/stdc++.h>
using namespace std;
const int MAXN = 810;
int dist[MAXN][MAXN], marc[MAXN][MAXN];
int dist_bee[MAXN][MAXN], marc_bee[MAXN][MAXN];
char a[MAXN][MAXN];
int n, s;
pair<int, int> st, en;
vector<pair<int, int>> bees;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
bool in(int i, int j){
return 0 < i && i <= n && 0 < j && j <= n;
}
void bfs_bees(){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
dist_bee[i][j] = 1e9;
}
}
queue<pair<int, int>> q;
for(auto [i, j] : bees) q.push({i, j}), dist_bee[i][j] = 0, marc_bee[i][j] = 1;
while(!q.empty()){
auto [i, j] = q.front(); q.pop();
for(int k=0; k<4; k++){
int ni = i + dx[k], nj = j + dy[k];
if(!in(ni, nj) || marc_bee[ni][nj] || a[ni][nj] == 'T' || a[ni][nj] == 'D') continue;
marc_bee[ni][nj] = 1;
dist_bee[ni][nj] = dist_bee[i][j] + 1;
q.push({ni, nj});
}
}
}
bool check(int t){
if(t < 0) return true;
if(dist_bee[st.first][st.second] <= t) return false;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
dist[i][j] = 1e9;
marc[i][j] = 0;
}
}
queue<pair<int, int>> q;
q.push(st); dist[st.first][st.second] = 0; marc[st.first][st.second] = 1;
while(!q.empty()){
auto [i, j] = q.front(); q.pop();
for(int k=0; k<4; k++){
int ni = i + dx[k], nj = j + dy[k];
if(!in(ni, nj) || marc[ni][nj] || a[ni][nj] == 'T') continue;
if(dist_bee[ni][nj] <= t + (dist[i][j] + 1) / s) continue;
marc[ni][nj] = 1;
dist[ni][nj] = dist[i][j] + 1;
q.push({ni, nj});
}
}
return marc[en.first][en.second];
}
int bs(){
int l = -1, r = n * n;
while(l < r){
int m = l + (r - l + 1) / 2;
if(check(m)) l = m;
else r = m - 1;
}
return l;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> a[i][j];
if(a[i][j] == 'M') st = {i, j};
if(a[i][j] == 'D') en = {i, j};
if(a[i][j] == 'H') bees.push_back({i, j});
}
}
bfs_bees();
cout << bs() << "\n";
return 0;
}
