#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n, k, dy[4]={0, 0, -1, 1}, dx[4]={1, -1, 0, 0};
vector<string> graph;
bool can(int mid){
int ex, ey;
queue<pii> bee, bear, nbee, nbear;
vector<vector<bool> > visited(n, vector<bool>(n, 0)), vbear(n, vector<bool>(n, 0));
for (int i=0; i<n; ++i)for (int j=0; j<n; ++j){
if (graph[i][j]=='H')visited[i][j]=1, bee.push(mp(i, j));
else if (graph[i][j]=='D')ex=i, ey=j;
}
while (mid--){
while (bee.size()){
int x=bee.front().fi, y=bee.front().se;
bee.pop();
for (int i=0; i<4; ++i){
int nx=x+dx[i], ny=y+dy[i];
if (nx<0||ny<0||nx>=n||ny>=n||graph[nx][ny]=='T'||graph[nx][ny]=='D'||visited[nx][ny])continue;
visited[nx][ny]=1;
nbee.push(mp(nx, ny));
}
}
swap(bee, nbee);
}
for (int i=0; i<n; ++i)for (int j=0; j<n; ++j)if (graph[i][j]=='M'){
if (visited[i][j])return 0;
else vbear[i][j]=1, bear.push(mp(i, j));
}
while (bear.size()){
for (int ooga=0; ooga<k; ++ooga){
while (bear.size()){
int x=bear.front().fi, y=bear.front().se;
bear.pop();
if (visited[x][y])continue;
for (int i=0; i<4; ++i){
int nx=x+dx[i], ny=y+dy[i];
if (nx<0||ny<0||nx>=n||ny>=n||graph[nx][ny]=='T'||visited[nx][ny]||vbear[nx][ny])continue;
vbear[nx][ny]=1;
nbear.push(mp(nx, ny));
}
}
swap(bear, nbear);
}
while (bee.size()){
int x=bee.front().fi, y=bee.front().se;
bee.pop();
for (int i=0; i<4; ++i){
int nx=x+dx[i], ny=y+dy[i];
if (nx<0||ny<0||nx>=n||ny>=n||graph[nx][ny]=='T'||graph[nx][ny]=='D'||visited[nx][ny])continue;
visited[nx][ny]=1;
nbee.push(mp(nx, ny));
}
}
swap(bee, nbee);
}
return vbear[ex][ey];
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
graph.resize(n);
for (int i=0; i<n; ++i)cin>>graph[i];
int low=-1, high=n*n+1;
while (low+1<high){
int mid=(low+high)/2;
if (can(mid))low=mid;
else high=mid;
}
cout<<low;
}
