// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define ll long long
#define nl '\n'
/*
Mecho can only walk on grass and cannot go through trees or hives, and he can make at most S steps per minute.
every minute
he eats or
he leaves immediately and takes up to S steps through the forest as described above
bees spread to grassy cells
trees = no one can go there
m = mecho, grassy cells => i will replace with g
g = grassy
d = mecho home; bees cannot go / pass here
h = hive
*/
const int N = 810;
char grid[N][N];
int stepsMecho[N][N], stepsBee[N][N];
int n, s;
array<int, 2> Mecho, MechoHouse;
vector<array<int, 2>> Bee;
vector<array<int,2>> moves = {{-1,0},{1,0},{0,-1},{0,1}};
struct m{
bool isMecho;
int x,y;
};
bool good(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n && grid[x][y] != 'T';
}
bool isHome(int x, int y) {
return x == MechoHouse[0] && y == MechoHouse[1];
}
void debug() {
cout << "Mecho: " << nl;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
cout << stepsMecho[i][j] << " ";
}
cout << nl;
}
cout << "Bees: " << nl;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
cout << stepsBee[i][j] << " ";
}
cout << nl;
}
}
/*
bool bs(int steps) {
memset(stepsMecho,-1,sizeof(stepsMecho));
memset(stepsBee,-1,sizeof(stepsBee));
queue<m> q, q2;
q2.push(m{true,Mecho[0],Mecho[1]});
stepsMecho[Mecho[0]][Mecho[1]] = 0;
for (auto [x,y]:Bee) {
q.push(m{false,x,y});
stepsBee[x][y]=0;
}
while(!q.empty()) {
m v = q.front(); q.pop();
if (stepsBee[v.x][v.y] == steps) { q2.push(v); continue; }
for (auto [addx,addy]: moves) {
int nx = v.x + addx, ny = v.y + addy;
if (good(nx,ny) && !isHome(nx,ny) && stepsBee[nx][ny] == -1) {
q.push(m{false,nx,ny});
stepsBee[nx][ny] = stepsBee[v.x][v.y]+1;
}
}
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (stepsBee[i][j] != -1)
stepsBee[i][j] = 0;
while(!q2.empty()) {
m v = q2.front(); q2.pop();
// if (steps==1) {
// cout << v.isMecho << " " << v.x << " " << v.y << nl;
// debug();
// cout << nl;
// }
if (v.isMecho) {
if (stepsBee[v.x][v.y] != -1 && stepsBee[v.x][v.y] <= (stepsMecho[v.x][v.y]+s-1)/s) { continue; }
for (auto [addx,addy]: moves) {
int nx = v.x + addx, ny = v.y + addy;
if (good(nx,ny) && stepsMecho[nx][ny] == -1 && (stepsBee[nx][ny] == -1 || stepsBee[nx][ny] > (stepsMecho[v.x][v.y]+s)/s)) {
if (isHome(nx,ny)) { return 1; }
stepsMecho[nx][ny] = stepsMecho[v.x][v.y]+1;
q2.push(m{true,nx,ny});
}
}
} else {
for (auto [addx,addy]: moves) {
int nx = v.x + addx, ny = v.y + addy;
if (good(nx,ny) && !isHome(nx,ny) && stepsBee[nx][ny] == -1) {
q2.push(m{false,nx,ny});
stepsBee[nx][ny] = stepsBee[v.x][v.y]+1;
}
}
}
}
return 0;
}
*/
void reset() {
memset(stepsMecho,-1,sizeof(stepsMecho));
}
bool bs(int steps) {
if (stepsBee[Mecho[0]][Mecho[1]] != -1 && stepsBee[Mecho[0]][Mecho[1]] <= steps) return 0;
reset();
queue<array<int,2>> q;
q.push(Mecho);
stepsMecho[Mecho[0]][Mecho[1]] = 0;
while(!q.empty()) {
auto [x,y] = q.front(); q.pop();
for (auto [px,py]:moves) {
int nx = x + px, ny = y + py;
if (good(nx,ny) && stepsMecho[nx][ny] == -1 && (stepsMecho[x][y] + 1) / s < (stepsBee[nx][ny] - steps)) {
stepsMecho[nx][ny] = stepsMecho[x][y]+1;
q.push({nx,ny});
}
}
}
for (auto [px,py]:moves) {
int nx = MechoHouse[0] + px, ny = MechoHouse[1] + py;
if (good(nx,ny) && stepsMecho[nx][ny] != -1) return 1;
}
return 0;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
memset(stepsBee,-1,sizeof(stepsBee));
cin >> n >> s;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) {
cin >> grid[i][j];
if (grid[i][j]=='M') {
grid[i][j] = 'G';
Mecho = {i,j};
}
if (grid[i][j]=='H') {
Bee.pb({i,j});
}
if (grid[i][j]=='D') {
MechoHouse = {i,j};
}
}
queue<array<int,2>> q;
for (auto [x,y]:Bee) {
q.push({x,y});
stepsBee[x][y] = 0;
}
while(!q.empty()) {
auto [x,y] = q.front(); q.pop();
for (auto [px,py]:moves) {
int nx = x + px, ny = y + py;
if (good(nx,ny) && stepsBee[nx][ny] == -1 && !isHome(nx,ny)) {
stepsBee[nx][ny] = stepsBee[x][y]+1;
q.push({nx,ny});
}
}
}
int lo = 0, hi = 1e9;
while(lo<=hi) {
int mid = (lo+hi)/2;
if (bs(mid)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << lo-1;
}
