#include <bits/stdc++.h>
using namespace std ;
const int N = 800 ;
int dx[]{0 , 0 , 1 , -1} ;
int dy[]{1 , -1 , 0 , 0} ;
int n , s ;
pair <int , int> Honey , Home ;
char a[N][N] ;
bool inside(int x , int y) {
return (x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 'T') ;
}
bool val(int x , int y) {
return x / s < y ;
}
bool ok(int time) {
vector<vector<int>> mn2(n , vector<int>(n , 1e9)) ;
queue<pair <int , int>> q2 ;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
if(a[i][j] == 'H') {
q2.push({i, j}) ;
mn2[i][j] = 0 ;
}
}
}
while(q2.size()) {
pair <int , int> t = q2.front() ;
q2.pop() ;
for(int i = 0 ; i < 4 ; i++) {
int x = t.first + dx[i] ;
int y = t.second + dy[i] ;
if(inside(x , y) && mn2[t.first][t.second] + 1 < mn2[x][y]) {
mn2[x][y] = mn2[t.first][t.second] + 1 ;
q2.push({x, y}) ;
}
}
}
vector<vector<int>> mn(n , vector<int>(n , 1e9)) ;
queue <pair <int , int>> q ;
mn[Honey.first][Honey.second] = 0 ;
if(mn2[Honey.first][Honey.second] > time)
q.push(Honey) ;
while(!q.empty()) {
pair <int , int> t = q.front() ;
q.pop() ;
for(int i = 0 ; i < 4 ; i++) {
int x = t.first + dx[i] ;
int y = t.second + dy[i] ;
if(val(mn[t.first][t.second] + 1 , mn2[x][y] - time) && inside(x , y) && mn[t.first][t.second] + 1 < mn[x][y]) {
mn[x][y] = mn[t.first][t.second] + 1 ;
q.push({x , y}) ;
}
}
}
for(int i = 0 ; i < 4 ; i++){
int x = Honey.first + dx[i] ;
int y = Honey.second + dy[i] ;
if(inside(x , y) && val(mn[x][y] , mn2[x][y] - time))
return true ;
}
return false ;
}
int main() {
cin >> n >> s ;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
cin >> a[i][j] ;
if(a[i][j] == 'M')
Honey = {i , j} ;
if(a[i][j] == 'D')
Home = {i , j} ;
}
}
int l = 0 , r = n * n + 1 ;
while(l + 1 < r) {
int m = (l + r) / 2 ;
if(ok(m))
l = m ;
else
r = m ;
}
cout << l - 1 << endl ;
}
