#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, s;
vector<vector<char>> mp;
pair<int, int> m;
vector<vector<int>> bee_dist;
int bear_dist[805][805];
vector<pair<int, int>> allowed_moves{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool check(int eat){
queue<pair<int, int>> bear;
memset(bear_dist, -1, sizeof(bear_dist));
bear_dist[m.first][m.second] = 0;
bear.push(m);
while(!bear.empty()){
pair<int, int> pos = bear.front();
bear.pop();
if(bear_dist[pos.first][pos.second]/s + eat >= bee_dist[pos.first][pos.second])continue;
for(pair<int, int> u : allowed_moves){
int x = pos.first + u.first, y = pos.second + u.second;
if(x > 0 && x < n+1 && y > 0 && y < n+1 && mp[x][y]=='D')return true;
if(bear_dist[x][y]==-1 && x > 0 && x < n+1 && y > 0 && y < n+1 && mp[x][y] != 'D' && mp[x][y] != 'T'){
bear_dist[x][y]=bear_dist[pos.first][pos.second] + 1;
bear.push({x, y});
}
}
}
return false;
}
signed main(){
cin >> n >> s;
mp.resize(n+2, vector<char>(n+2));
bee_dist.resize(n+2, vector<int>(n+2, INF));
queue<pair<int, int>> bees;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> mp[i][j];
if(mp[i][j]=='M')m={i, j};
else if(mp[i][j]=='H'){
bees.push({i, j});
bee_dist[i][j]=0;
}
}
}
while(!bees.empty()){
pair<int, int> pos = bees.front();
bees.pop();
for(pair<int, int> u : allowed_moves){
int x = pos.first+u.first, y = pos.second+u.second;
if(bee_dist[x][y]==INF && x > 0 && x < n+1 && y > 0 && y < n+1 && mp[x][y]!= 'D' && mp[x][y] != 'T'){
bee_dist[x][y] = bee_dist[pos.first][pos.second]+1;
bees.push({x, y});
}
}
}
int l = -1, r = n*n;
while(l<r){
int mid = (l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout << l << "\n";
}
