#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int oo = 1e9 + 9;
const int MAX = 801;
struct cord{
int x = 0, y = 0;
cord(int x1, int y1){
x = x1;
y = y1;
}
};
pii dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, s;
cord start(0, 0), dest(0, 0);
char grid[MAX][MAX];
int beeTime[MAX][MAX];
bool inBounds(cord c){
return c.x >= 0 && c.x < n && c.y >= 0 && c.y < n;
}
void bfs1(vector<cord>& source){
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
beeTime[i][j] = oo;
}
}
queue<cord> q;
for(cord a:source){
q.push(a);
beeTime[a.x][a.y] = 0;
}
while(!q.empty()){
cord c = q.front();
q.pop();
for(auto &d:dir){
cord c1 = cord(c.x + d.first, c.y + d.second);
if(!inBounds(c1) || grid[c1.x][c1.y] == 'T' || grid[c1.x][c1.y] == 'D') continue;
if(beeTime[c1.x][c1.y] > beeTime[c.x][c.y] + 1){
beeTime[c1.x][c1.y] = beeTime[c.x][c.y] + 1;
q.push(c1);
}
}
}
}
bool visited[MAX][MAX];
bool check(int startTime){
memset(visited, 0, sizeof(visited));
visited[start.x][start.y] = 1;
queue<pair<cord, pii>> q;
q.push({start, {startTime, s}});
while(!q.empty()){
cord c = q.front().first;
pii t = q.front().second;
q.pop();
if(grid[c.x][c.y] == 'D') return true;
if(beeTime[c.x][c.y] <= t.first) continue;
for(auto d:dir){
cord c1 = cord(c.x + d.first, c.y + d.second);
if(!inBounds(c1) || grid[c1.x][c1.y] == 'T' || visited[c1.x][c1.y] == 1) continue;
visited[c1.x][c1.y] = 1;
if(t.second == 1){
q.push({c1, {t.first + 1, s}});
}
else{
q.push({c1, {t.first, t.second - 1}});
}
}
}
return false;
}
int main(){
cin >> n >> s;
vector<cord> bees;
getchar();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
char c = getchar();
grid[i][j] = c;
if(c == 'H'){
bees.push_back(cord(i, j));
}
else if(c == 'M'){
start = cord(i, j);
}
else if(c == 'D'){
dest = cord(i, j);
}
}
getchar();
}
bfs1(bees);
int l = 0, r = n * n;
int ans = -1;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid)){
ans = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
cout << ans << '\n';
}
