#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int N = 800;
vector<pii>path = {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}};
int n, s;
char grid[N][N];
int bees[N][N];
bool vis[N][N];
int dist[N][N];
int sr, sc;
int dr, dc;
queue<pii>Q;
queue<pair<int, pii>>q;
bool Valid(int i, int j){
return (i>=0 && j>=0 && i<n && j<n);
}
bool check(int wait){
memset(vis, false, sizeof(vis));
memset(dist, -1, sizeof(dist));
q.push({sr, {sc, 0}}); dist[sr][sc] = wait;
while(!q.empty()){
int i = q.front().first;
int j = q.front().second.first;
int cnt = q.front().second.second;
q.pop();
if(dist[i][j] == -1) continue;
for(pii it: path){
int x = i + it.first; int y = j + it.second;
int distXY = dist[i][j] + ((cnt+1)%s == 0);
if(Valid(x, y) && !vis[x][y] && grid[x][y] != 'T' && ((distXY < bees[x][y] && bees[x][y] != -1) || bees[x][y] == -1)){
dist[x][y] = distXY;
vis[x][y] = true;
q.push({x, {y, cnt+1}});
}
}
}
if(dist[dr][dc] == -1) return false;
else return true;
}
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin>>n>>s;
memset(bees, -1, sizeof(bees));
for(int i = 0; i<n; i++){
string s; cin>>s;
for(int j = 0; j<n; j++){
grid[i][j] = s[j];
if(grid[i][j] == 'M'){
sr = i; sc = j;
}else if(grid[i][j] == 'D'){
dr = i; dc= j;
}else if(grid[i][j] == 'H'){
Q.push({i, j}); bees[i][j] = 0; vis[i][j] = true;
}
}
}
while(!Q.empty()){
int i = Q.front().first;
int j = Q.front().second;
Q.pop();
for(pii it: path){
int x = i + it.first; int y = j + it.second;
if(Valid(x, y) && !vis[x][y] && grid[x][y] != 'T' && grid[x][y] != 'D'){
vis[x][y] = true;
bees[x][y] = bees[i][j] + 1;
Q.push({x, y});
}
}
}
int l = 0, h = 2*n;
int ans = -1;
while(l<=h){
int mid = l + (h-l)/2;
if(check(mid)){
l = mid+1;
ans = mid;
}else{
h = mid-1;
}
}
cout<<ans;
}
