#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int n, s;
char grid[800][800];
int distb[800][800];
bool vis[800][800];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int homex, homey;
int honx, hony;
bool inside1(pair<int, int> p){
return p.first >= 0 && p.first < n && p.second >= 0 && p.second < n;
}
bool inside2(pair<int, int> p){
return p.first >= 0 && p.first < n && p.second >= 0 && p.second < n && grid[p.first][p.second] != 'H'
&& grid[p.first][p.second] != 'T';
}
int main()
{
queue<pair<int, int>> q;
cin >> n >> s;
for(int i = 0; i < n; i++){
string line;
cin >> line;
for(int j = 0; j < n; j++){
grid[i][j] = line[j];
distb[i][j] = 2*n;
if(grid[i][j] == 'H'){
q.push({i, j});
distb[i][j] = 0;
}
if(grid[i][j] == 'D'){
homex = i;
homey = j;
}
if(grid[i][j] == 'M'){
honx = i;
hony = j;
}
}
}
while(!q.empty()){
auto x = q.front();
q.pop();
for(int i = 0; i < 4; i++){
pair<int, int> y = {x.first + dx[i], x.second + dy[i]};
if(inside1(y) && distb[x.first][x.second] + 1 < distb[y.first][y.second]){
distb[y.first][y.second] = distb[x.first][x.second] + 1;
q.push({y.first, y.second});
}
}
}
vis[homex][homey] = true;
queue<tuple<int, int, int>> deq; // x, y, moves
queue<tuple<int, int, int>> deq1; // x, y, moves
deq.push({homex, homey, 0});
int mins = distb[homex][homey] - 1;
bool stop = false;
while(mins >= 0){
while(!deq.empty()){
auto t = deq.front();
if(get<0>(t) == honx && get<1>(t) == hony){
stop = true;
break;
}
deq1.push({get<0>(t), get<1>(t), 0});
deq.pop();
if(get<2>(t) < s){
for(int i = 0; i < 4; i++){
pair<int, int> y = {get<0>(t) + dx[i], get<1>(t) + dy[i]};
if(inside2(y) && !vis[y.first][y.second] && distb[y.first][y.second] > mins){
vis[y.first][y.second] = true;
deq.push({y.first, y.second, get<2>(t) + 1});
}
}
}
}
if(stop) break;
deq = deq1;
deq1 = queue<tuple<int, int, int>>();
mins --;
}
cout << mins << endl;
}
