#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int nx = 805;
int n, s, l=0, r=2000, md, ans=-1;
string grid[nx];
pair<int, int> bear, home, dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
set<pair<int, int>> bee;
bool check(int steps){
vector<vector<bool>> bg(nx, vector<bool>(nx, false));
queue<pair<int, pair<int, int>>> q, bq;
for(auto [y, x] : bee) q.push({0, {y, x}});
while(q.front().ff<md){
int mins = q.front().ff;
pair<int, int> pos = q.front().ss;
q.pop();
for(int i=0; i<4; i++){
if(pos.ff+dir[i].ff>=0 && pos.ff+dir[i].ff<n && pos.ss+dir[i].ss>=0 && pos.ss+dir[i].ss<n){
if(pos.ff+dir[i].ff==bear.ff && pos.ss+dir[i].ss==bear.ss) return false;
else if(!bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss]){
q.push({mins+1, {pos.ff+dir[i].ff, pos.ss+dir[i].ss}});
bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss] = true;
}
}
}
}
bq.push({0, {bear.ff, bear.ss}});
int bcnt=md+1, brcnt=steps;
while(!bq.empty()){
while(bq.front().ff<brcnt){
int mins = bq.front().ff;
pair<int, int> pos = bq.front().ss;
bq.pop();
if(bg[pos.ff][pos.ss]) continue;
for(int i=0; i<4; i++){
if(pos.ff+dir[i].ff>=0 && pos.ff+dir[i].ff<n && pos.ss+dir[i].ss>=0 && pos.ss+dir[i].ss<n){
if(pos.ff+dir[i].ff==home.ff && pos.ss+dir[i].ss==home.ss) return true;
else if(!bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss]){
bq.push({mins+1, {pos.ff+dir[i].ff, pos.ss+dir[i].ss}});
}
}
}
} brcnt+=steps;
while(q.front().ff<bcnt){
int mins = q.front().ff;
pair<int, int> pos = q.front().ss;
q.pop();
for(int i=0; i<4; i++){
if(pos.ff+dir[i].ff>=0 && pos.ff+dir[i].ff<n && pos.ss+dir[i].ss>=0 && pos.ss+dir[i].ss<n){
if(pos.ff+dir[i].ff==bear.ff && pos.ss+dir[i].ss==bear.ss) return false;
else if(!bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss]){
q.push({mins+1, {pos.ff+dir[i].ff, pos.ss+dir[i].ss}});
bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss] = true;
}
}
}
}
}
return false;
}
int main(){
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> s;
for(int i=0; i<n; i++){
cin >> grid[i];
for(int j=0; j<n; j++){
if(grid[i][j]=='H') bee.insert({i, j});
else if(grid[i][j]=='M') bear = {i, j};
else if(grid[i][j]=='D') home = {i, j};
}
}
while(l<=r){
md = l+(r-l)/2;
if(check(s)){
ans = md;
l = md+1;
} else r = md-1;
}
cout << ans-1;
return 0;
}
